MENU

堆及其相关应用

August 6, 2018 • Read: 345 • 算法

什么是堆?

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

总结

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

最后编辑于: October 7, 2018
Archives Tip
QR Code for this page
Tipping QR Code
Leave a Comment