什么是堆

首先堆是一个完全二叉树,但同时他具有这样的要求:每一个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;每一个结点的值都小于或等于其左右孩子结点的值,称为小顶堆

如下图是一个大顶堆
这里写图片描述

在此要补充一个二叉树的性质:二叉树的某个节点下标为i,则它的左孩子的下标一定为2i,右孩子下标一定为2i+1。

案列分析

假如现在我们要对这个序列,{50,10,90,30,70,40,80,60,20}进行堆排序,我们现在要做的:
1. 首先我们要把这个无序序列变成一个堆,构成堆之后,由堆的定义我们知道,堆的根节点一定是整个树当中值最大的。
2. 变成堆后,根节点和树的最后一个结点交换位置,然后弹出该节点,剩下的结点再重新构造成一个新堆。

上述两步关键代码

//具体构建堆的逻辑代码 
void heapAdjust(SqList *L, int s, int m){ 
    int temp, j; 
    temp = L->r[s]; 
    for(j=2*s;j<=m;j*=2){ 
 
        if(j<m && L->r[j] < L->r[j+1]){ 
            ++j; 
        } 
 
        if(temp >= L->r[j]){ 
            break; 
        } 
 
        L->r[s] = L->r[j]; 
        s=j; 
    } 
    L->r[s] = temp; 
} 
 
//排序  
void heapSort(SqList *L){ 
    int i; 
    //先把序列转换为堆  
    for(i = L->length/2; i>0; i--){ 
        heapAdjust(L, i, L->length); 
    } 
    //没交换一次,就转换一次为堆  
    for(i = L->length;i>1;i--){ 
        swap(L, 1, i); 
        heapAdjust(L, 1, i-1); 
    }  
}

说一说heapAdjust这个方法的关键逻辑

  1. 首先根据传入的下标,获得一个结点,开始对这个结点操作;
  2. 然后根据这个结点,获取到它的左右孩子结点(上面提到的二叉树定义:左孩子为2i, 右孩子为2i+1);
  3. 左右孩子比较,得出值大者跟其父节点交换位置。

初始无序序列树图:
这里写图片描述

例如,当i=length/2=4时,获取到的结点为30,然后再获取30的左右孩子分别为60,20。由于60大于30,因此30和60交换位置。

这里写图片描述

最后转换为堆之后的示意图:

这里写图片描述

完整代码

public class HeapSort { 
 
    /** 
     * 从小到大排列,就是维护一个大根堆 
     * 从大到小排列,就是维护一个小根堆 
     */ 
    public void sort(int[] array){ 
        int size = array.length - 1; 
        //首先构造根堆(即把最大的或者最小的放在根节点)为什么i为size/2,因为构造堆从底向上 
        for(int i = size / 2; i > 0; i--){ 
            heapAdjust(array, i, size); 
        } 
        for(int i = size; i > 0; i--){ 
            swap(array, 1, i); 
            heapAdjust(array, 1, i-1); 
        } 
    } 
 
    public  void heapAdjust(int[] array, int root, int end){ 
        int temp = array[root]; 
        for(int i = root * 2; i <= end; i*=2){ 
            if(i < end && array[i] < array[i+1]){ 
               i++; 
            } 
            if(temp >= array[i]){ 
                break; 
            } 
            array[root] = array[i]; 
            root = i; 
        } 
        array[root] = temp; 
    } 
 
    public void swap(int[] array, int i, int j){ 
        int temp = array[i]; 
        array[i] = array[j]; 
        array[j] = temp; 
    } 
 
    public static void main(String args[]){ 
        int array[] = new int[]{0,50,10,90,30,70,40,80,60,20}; 
        new HeapSort().sort(array); 
 
        for(int i = 1; i < array.length; i++){ 
            System.out.print(array[i] + " "); 
        } 
    } 
}

结果:

这里写图片描述

时间复杂度

建堆的时间复杂度:O(n)
排序的时间复杂度:
for循环肯定是n的,关键是看heapAdjust,一开始传1,n进去,我们看heapAdjust里的时间复杂度是多少
完全二叉树的性质:

有n个节点的完全二叉树,深度为 log n(向上取整) + 1

因此传1,n进去,假设n为9,那么此时会查找的节点下标为1,2,4,8,也就是走完了整个树n个节点的深度(二分查找)
所以heapAdjust的时间复杂度为:O(logn)
所以假如维护k的堆,heapAdjust的时间复杂度为:O(logk)

发布评论

分享到:

IT虾米网

微信公众号号:IT虾米 (左侧二维码扫一扫)欢迎添加!

经典排序算法:希尔排序(Shell Sort)详解
你是第一个吃螃蟹的人
发表评论

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。