用数组构造最大堆结构

题目

输入一个一维数组，构造最大堆结构。
例如：
输入数组：[4,6,7,3,4,0,1,8,11,10]，输出结果：[11,10,7,8,4,0,1,6,3,4]

解析

关于堆排序可以参考堆排序。这里一维数组表示堆结构，然后调整元素顺序构造一个最大堆结构。

一维数组如何表示堆结构

如果父节点存在在索引index处，那么它的左孩子索引为2*index+1，右孩子索引为2*index+2。数组的坐标从0开始，也就是根节点是坐标为0的元素。

构造最大堆步骤

1. 定义一个函数maxHeapify()，调整堆中父节点和子节点的位置，保证当前节点和其子节点满足最大堆的性质。假设子节点比父节点大，与父节点进行交换，子节点记为Child。
2. 函数maxHeapify()递归调用向下继续调整变动了的子节点Child，此时节点Child为父节点，去调整其与孩子节点的位置关系，依次递归直到叶子节点。
3. 定义构造最大堆函数buildMaxHeap()，循环从非叶子节点起调用函数maxHeapify()，直到根节点为止。

代码

public class HeapSort {
    //构造最大堆函数
    public boolean buildMaxHeap(int[] array){
        if (null == array || 0 == array.length){
            return false;
        }
        //循环从非叶子节点起调用函数maxHeapify()，直到根节点为止。
        for (int j = (array.length/2); j >= 0; j--){
            maxHeapify(j, array);
        }
        return true;
    }
    //调整堆中父节点和子节点的位置，保证当前节点和其子节点满足最大堆的性质
    private void maxHeapify(int index, int[] array){
        int l = leftChild(index);
        int r = rightChild(index);
        int largest = index;
        if (l < array.length){
            if (array[l] > array[largest]){
                largest = l;
            }
        }
        if (r < array.length){
            if (array[r] > array[largest]){
                largest = r;
            }
        }
        //继续调整变动了的子节点
        if (largest != index){
            //交换父节点与子节点的位置
            int temp = array[largest];
            array[largest] = array[index];
            array[index] = temp;
            //此时子节点为父节点，去调整其与孩子节点的位置关系
            //依次递归直到叶子节点
            maxHeapify(largest, array);
        }
    }

    //左孩子
    private int leftChild(int index){
        return index * 2 + 1;
    }

    //右孩子
    private int rightChild(int index){
        return index * 2 + 2;
    }

    //测试用例
    public static void main(String[] args){
        int[] array = {4,6,7,3,4,0,1,8,11,10};
        HeapSort sort = new HeapSort();
        sort.buildMaxHeap(array);
        for (int i = 0; i < array.length; ++i){
            System.out.println(array[i]);
        }
    }
}