堆排序及其时间复杂度分析

public class HeapUtil {

    /**
     * Heap数据结构是由列表或者数组抽象而来
     * 这个数据结构可以看作是一个不完整的二叉树
     * 规定列表的第一个元素为二叉树的根结点
     * 并且假设 parentIndex = i,则leftChildIndex = 2*i,rightChildIndex = 2*i + 1
     * 1<=index<=array.legnth + 1
     *
     * 最大堆的定义是对于array[parentIndex] >= array[leftChildIndex] && array[parentIndex] >= array[rightChildIndex]
     * 最小堆则相反
     * T(N) = O(logN)
     * @param array
     * @param index
     */
    public static void maxHeapify(int[] array, int index, int startIndex, int endIndex){
        int leftChildIndex = (index + 1) * 2;
        int rightChildIndex = leftChildIndex + 1;

        if(leftChildIndex > endIndex + 1) {
            //说明是叶子结点
            return ;
        }

        int turnWhere = 0;

        int maxValOfChildren = rightChildIndex > endIndex + 1 ? array[leftChildIndex - 1]
                : Math.max(array[leftChildIndex - 1], array[rightChildIndex - 1]);

        if(array[index] >= maxValOfChildren){
            //没必要交换
            return;
        }else{
            //0:根节点和左边互换
            //1:根节点和右边互换
            if(rightChildIndex <= endIndex + 1 && maxValOfChildren == array[rightChildIndex - 1]){
                turnWhere = 1;
                int temp = array[index];
                array[index] = array[rightChildIndex - 1];
                array[rightChildIndex - 1] = temp;
            }else{
                int temp = array[index];
                array[index] = array[leftChildIndex - 1];
                array[leftChildIndex - 1] = temp;
            }

        }

        if(turnWhere == 0){
            maxHeapify(array, leftChildIndex - 1, startIndex, endIndex);
        }else{
            maxHeapify(array, rightChildIndex - 1, startIndex, endIndex);
        }
    }

    /**
     * 将一个数组转换成一个最大堆
     * T(N) = O(N)
     * 这个时间复杂度不能简单的看作O(NlogN)
     * 对于长度为N的数组,(我们不考虑不完整二叉树的情况),有N/2个叶子节点
     * 对于叶子节点的父节点来说maxHeapify实际上只需要做一次交换即可
     * 同理对于叶子节点的父节点的父节点来说maxHeapify实际上只需要做2次交换
     * 所以对于一个深度为L的二叉树,做一次maxHeapify实际包含的O(1)操作为L次
     * 那么对于N/4(叶子结点总数为N/2则其父节点个数为N/4)个深度为1的父节点运行的时间为N/4 * C(C表示常数时间)
     * 对于N/8个深度为2的父节点运行的时间为N/8 * 2 * C
     * .
     * .
     * .
     * 对于根结点来说,只有一个并且深度为lgN运行时间为1 * lgN * C
     * 则T(N) = N/4 * 1 * C + N/8 * 2 * C + N/16 * 3 * C + ... + 1 * lgN * C
     * 为了更好的表示我们假设N/4=2^k
     * 则buildMaxHeapFromArray的运行时间可以表示为
     * C * 2^k * (1/2^0 + 2/2^1 + 3/2^2 + ... + (k+1)/2^k)
     * (1/2^0 + 2/2^1 + 3/2^2 + ... + (k+1)/2^k)是一个有上界的常数
     * 则T(N) = C * N/4 = O(N)
     */
    public static void buildMaxHeapFromArray(int[] array, int startIndex, int endIndex){
        //问题1:为什么从n/2开始
        //因为对于任何长度为n的数组A,A[n/2 + 1......n]都是叶子节点
        //所以n/2是最后一个非叶子节点,以该节点为根结点的局部二叉树的深度=1
        for (int i = (endIndex - startIndex + 1) / 2; i >= startIndex; i--) {
            maxHeapify(array, i, startIndex, endIndex);
        }
    }

    /**
     * 通过最大堆使得输入的无序数组array排序
     * @param array
     * @return
     */
    public static int[] heapSort(int[] array){
        int[] sortedArray = new int[array.length];

        for (int i = 0; i < sortedArray.length; i++) {
            //step1.构造最大堆
            buildMaxHeapFromArray(array, 0, array.length - i - 1);
            sortedArray[i] = array[0];
            array[0] = array[array.length - i - 1];
        }

        for (int i = 0; i < array.length; i++) {
            System.out.print(sortedArray[i] + ",");
        }

        return null;
    }

    public static void main(String args[]) {
        heapSort(new int[] {21, 14, 10, 15, 33, 2, 3, 16, 4, 1});
    }


}

public class Node {

    public Node(int val, Node leftChild, Node rightChild){
        this.val = val;
        this.leftChild = leftChild;
        this.rightChild = rightChild;
    }

    private int val;


    private Node leftChild;


    private Node rightChild;

    /**
     * Getter method for property leftChild.
     *
     * @return property value of leftChild
     */
    public Node getLeftChild() {
        return leftChild;
    }

    /**
     * Setter method for property leftChild.
     *
     * @param leftChild value to be assigned to property leftChild
     */
    public void setLeftChild(Node leftChild) {
        this.leftChild = leftChild;
    }

    /**
     * Getter method for property rightChild.
     *
     * @return property value of rightChild
     */
    public Node getRightChild() {
        return rightChild;
    }

    /**
     * Setter method for property rightChild.
     *
     * @param rightChild value to be assigned to property rightChild
     */
    public void setRightChild(Node rightChild) {
        this.rightChild = rightChild;
    }

    /**
     * Getter method for property val.
     *
     * @return property value of val
     */
    public int getVal() {
        return val;
    }

    /**
     * Setter method for property val.
     *
     * @param val value to be assigned to property val
     */
    public void setVal(int val) {
        this.val = val;
    }
}