堆及其相关应用

什么是堆？

提到堆就不得不说到二叉树这个结构，堆就是一颗完全二叉树，什么叫完全二叉树，用一句话来概括就是：设二叉树的深度为h，除第h层外，其它各层的结点数都达到最大个数，第h层所有的结点都连续集中在最左边，这就是完全二叉树，举几个例子：

堆分两种，一种叫大根堆，一种叫小根堆。大根堆就是在堆结构中，任意一棵子树的根节点一定是最大值，举个例子：

看上图最左边的那颗树，他的子树有64323、643、423，而每一棵子树的根节点都是其子树的最大值，小根堆概念差不多，就是在堆结构中，任意一颗子树的根节点一定是最小值，就不举例了

构建大根堆

了解了堆的相应结构，接下来我们就要构建一个堆，我们用数组来实现堆结构，假如数组中的元素是012345，那么对应的树就是

直接给出关系：在数组不越界的前提下，任意一个下标i对应的根节点是(i-1)/2，左孩子是2×i+1，右孩子是2×i+2，当然，也包含特殊情况，比方说0本身就是根节点了，那么0的根节点就是(0-1)/2，在计算机中等于0，所以整棵树的根节点的根节点就是它本身

下面我们就要讲，给你一个数组，如何构建一个大根堆，假设这个数组的值是213604，我们定义一个下标i，表示0到i是一个大根堆

首先，i的初始值为0，那么数组中的2这个值就是一个大根堆，然后i++

到了1，因为1是小于1的根节点2的，所以1可以直接放到2的后面作为左孩子，此时大根堆为21，然后i++

到了3，因为3是大于根节点2的，所以将2和3交换位置，此时大根堆为312，然后i++

到了6，本来6应该放在1的后面作为1的左孩子，但是因为6比1大，所以6要和1进行交换，此时状态为3621，还没完，6还要继续和其根节点也就是3比较，6比3大，所以6还要和3交换，此时大根堆为6321,然后i++

到了0，0的根节点在数组中的下标是(4-1)/2=1，0的根节点是2，0比2小，所以直接放上取就行，此时大根堆为63210，然后i++

到了4，4的根节点在数组中的下标是(5-1)/2=2，4的根节点是2，4比2大，所以4要和2交换，此时状态为634102，然后4到了数组下标为2的位置，此时4的根节点是6，4比6小，所以不用交换，因为i已经等于了arr.length-1，所以整个数组已经变成大根堆了，如图

生成大根堆的时间复杂度是O(logN)，因为耗时的部分在于不断往上判断根节点与当前节点的关系，所以时间复杂度与高度成正比，而一个N个节点的完全二叉树高度是logN的，所以时间复杂度是O(logN)，代码如下：

代码

public class Heap {
    private static void heapSort(int[] arr) {
        if(arr == null || arr.length < 2) 
            return;
        for(int i = 0;i < arr.length;i++) {
            heapInsert(arr,i);//构建0-i的大根堆
        }
    }
    private static void heapInsert(int[] arr,int idx) {
        while(arr[idx] > arr[(idx - 1) / 2]) {
            swap(arr,idx,(idx - 1) / 2);
            idx = (idx - 1) / 2;
        }
    }
    private static void swap(int[] arr,int i,int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

改变大根堆

现在考虑这样一个问题，假设我已经构建好了一个大根堆，现在我将数组中的某一个值改变了，那么他就有可能不是一个大根堆了，我需要将改变后的数组重新变为一个大根堆，怎么做

假设原始大根堆是654352，现在我将6变为1，于是数组就变为154352，我现在要将其重新变为大根堆

先看该节点的左右两个孩子，找出两个孩子中较大的那个，然后和该节点进行比较，如果比当前节点大，就交换，对应样例就变成514352。然后重复该操作，就会变成554312，没有孩子了停止，大根堆也重新构建好了。代码如下：

代码

private static void heapify(int[] arr,int idx,int heapsize) {
    int left = 2 * idx + 1;
    while(left < heapsize) {
        int right = left + 1;
        int largest = right < heapsize && arr[right] > arr[left] ? right : left;
        largest = arr[largest] > arr[idx] ? largest : idx;
        if(largest == idx) 
            break;
        swap(arr,largest,idx);
        idx = largest;
        left = idx * 2 + 1;
    }
}

堆排序

1. 初始值i=1,n=arr.length
2. 对数组0~n-i范围内的值构建大根堆
3. 将数组第n-i值和第0值进行交换，++i，然后对0到arr.lenght~i的范围进行heapify操作
4. 重复2，3操作，直到i=n

代码

private static void heapSort(int[] arr) {
    if(arr == null || arr.length < 2) 
        return;
    for(int i = 0;i < arr.length;i++) 
        heapInsert(arr,i);//构建0-i的大根堆
    int heapsize = arr.length;
    swap(arr,0,--heapsize);
    while(heapsize > 0) {
        heapify(arr,0,heapsize);
        swap(arr,0,--heapsize);
    }
}

总结

左神说了一句话：“堆这个结构很重要，堆这个结构很重要，堆这个结构很重要......”