使用heapify方法构建堆

//package com.nowjava;//来 自 N o w  J a v a  . c o m


public class Main {

    /**

     * builds the heap using the heapify method

     * 

     * @param heap

     *            is the heap to be built

     * @param heapSize

     *            is the size of the heap

     */

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

        for (int i = heapSize / 2; i > 0; i--) {

            heapify(heap, i, heapSize);

        }

    }


    /**

     * 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;
        /*
        n o w j a v a . c o m - 时代Java 提 供
        */

        int rightIndex = 2 * index + 1;

        if (leftIndex <= heapSize) {

            if (heap[leftIndex].compareTo(heap[index]) > 0) {

                swap(heap, index, leftIndex);

                heapify(heap, leftIndex, heapSize);

            }

        }

        if (rightIndex <= heapSize) {

            if (heap[rightIndex].compareTo(heap[index]) > 0) {

                swap(heap, index, rightIndex);

                heapify(heap, rightIndex, heapSize);

            }

        }

    }