堆排序

//package com.nowjava;//时 代 J a v a 提 供


public class Main {

    public static void heapSort(Comparable[] heap, int heapSize) {

        for (int i = heapSize; i > 1; i--) {

            remove(heap, i);

        }

    }


    /**

     * remove will remove the element from heap

     * 

     * @param heap

     *            is the heap from which the element is to be removed

     * @param heapSize

     *            is the size of the heap

     * @return

     */

    public static Comparable remove(Comparable[] heap, int heapSize) {

        Comparable root = heap[1];

        swap(heap, 1, heapSize);

        heapify(heap, 1, heapSize - 1);

        return root;

    }


    /**

     * swap will swap the elements in heap at index and index2

     * 

     * @param heap

     *            is the heap to be switched

     * @param index

     *            is the first element to be switched

     * @param index2

     *            is the second element to be switched

     *//**来自 n o w  j a v a  . c o m**/

    public static void swap(Comparable[] heap, int index, int index2) {

        Comparable temp = heap[index];

        heap[index] = heap[index2];

        heap[index2] = temp;

    }


    /**

     * heapifies starting from a given node

     * 

     * heapifying checks each child of the node and if it is greater than the

     * parent it swaps the two and heapifies the child

     * 

     * @param heap

     *            the heap to heapify in

     * @param index

     *            the index of the node to heapify

     * @param heapSize

     *            the size of the heap

     */

    public static void heapify(Comparable[] heap, int index, int heapSize) {

        int leftIndex = 2 * index;

        int rightIndex = 2 * index + 1;

        if (leftIndex <= heapSize) {