堆及其相关应用

什么是堆？展开目录

提到堆就不得不说到二叉树这个结构，堆就是一颗完全二叉树，什么叫完全二叉树，用一句话来概括就是：设二叉树的深度为 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);
    }
}

总结展开目录

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