7.4.2 选择排序之堆排序

堆排序是一个树形选择排序方法，它的特点是：在排序过程中，将L[1...n]看成是一棵完全二叉树的顺序存储结构，

利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序区中选择关键字最大（或最小）的元素。

堆的定义如下：n个关键字序列L[1...n]称为堆，当且仅当该序列满足： ①L(i)<=L(2i)且L(i)<=L(2i+1)或②L(i)>L(2i)且L(i)>=L(2i+1)(1<=i<=[n/2])

满足第一种情况的堆称为小根堆（小顶堆），满足第二种情况的堆称为大根堆（大顶堆）。

如图所示是一个大根堆

算法思想：

堆排序的关键是构造初始堆，对于初始序列建堆，就是一个反复筛选的过程。

n个结点的完全二叉树，最后一个结点是第【n/2】个结点为根的孩子。

对第【n/2】个结点为根的子树筛选（对于大根堆：若根节点的关键字小于左右子女中关键字较大者，则交换），使该子树成为堆。

之后向前依次对各结点（【n/2】-1~1）为根的子树进行筛选，看该结点值是否大于其左右结点的值，若不是，将左右结点中较大值与之交换，交换后可能会破坏下一级的堆，于是继续采用上述方法构造下一级的堆，直到以该结点的子树构造成堆为止。

反复利用上述调整堆的方法建堆，直到根节点为止。

建立大根堆的算法：

<span style="font-size:18px;">void BuildMaxHeap(ElemType A[],int len){
    for(int i=len/2;i>0;i--){//从i=[n/2]~1,反复调整堆
        AdjustDown(A,i,len);
    }
}
void AdjustDown(ElemType A[],int k,int len){
//函数AdjustDown将元素i向下进行调整
    A[0]=A[k];//A[0]暂存

    for(i=2*k;i<=len;i*=2){//沿key较大的子节点向下筛选
        if(i<len&&A[i]<A[i+1]){//左孩子大于右孩子
            i++;//取key较大的子节点的下标
        }
        if(A[0]>=A[i]){//如果暂存大于其孩子结点，即满足大顶堆
            break;//筛选结束
        }else{ //如果暂存小于其孩子结点，即不满足大顶堆
            A[k]=A[i];//将A[i]调整到双亲结点
            k=i;//修改k值，以便继续向下筛选
        }
    }//for
    A[k]=A[0];//被筛选结点的值放入最终位置

}</span>

例如53,17,78,09,45,65,87,32

i=4 AdjustDown(A,4,8);

k=4 

A[0]=A[4]=09  

i=8 

8<8&&A[8]<A[9]==false 跳过

A[8]=32 A[0]<=A[8]==true

A[4]=A[0]=32; k=8

A[8]=A[0]=09

53,17,78,32,45,65,87,09

i=3 AdjustDown(A,3,8);

k=3

A[0]=A[3]=78

i=6

i<8&&A[6]<A[7]==true i=7 

A[0]>=A[7]==false 

A[3]=A[7]=87 k=7

A[7]=A[0]=78

53,17,87,32,45,65,78,09

i=2 AdjustDown(A,2,8);

k=2;

A[0]=A[2]=17

i=4

4<8&&A[4]<A[5]==true i=5

A[0]>A[5]==false A[2]=A[5]=45k=5

i=10 i>len 循环结束

A[5]=A[0]=17

53,45,87,32,17,65,78,09

i=1 AdjustDown(A,1,8);

k=1;

A[0]=A[1]=53

i=2

2<8&&A[2]<A[3]==true i=3

A[0]>A[3]==false A[1]=A[3]=87 k=i=3

i=6 6<8&&A[6]<A[7]==ture i=7

A[0]>=A[7]==false A[3]=A[7]=78 k=i=7

A[7]=A[0]=53

87,45,78,32,17,65,53,09

建堆的时间复杂度分析： 向下调整的时间与树高有关，为O(h).建堆过程中每向下调整时，大部分结点的高度都较小， 因此，可以证明在元素个数为N的序列上建堆，其时间复杂度为O(n),这说明可以在线性表时间内，将一个无序数组建成一个大顶堆。 堆排序算法分析： 应用这种数据结构进行排序的思路很简单，首先将存放在L[1...n]中的N个元素建成初始堆，由于堆本身的特点（以大根堆为例）堆顶元素就是最大值。 输出堆顶元素后，通常将堆底元素送入堆顶，此时根结点已经不满足大顶堆的性质，堆被破坏。 将堆顶向下调整使其继续保持大顶堆的性质，再输出堆顶元素，如此重复，直到堆中仅剩下一个元素为止。 堆排序算法： void HeapSort(Elemtype A[],int len){     BuildMaxHeap(A,len);//初始建堆     for(i=len;i>1;i--){//n-1趟的交换和建堆过程         Swap(A[i],A[1]);//输出堆顶元素（和堆底元素交换）         AdjustDown(A,1,i-1);//整理，把剩余的i-1个元素整理成堆     }//for } 同时，堆也支持删除和插入的操作。 由于堆顶元素或为最大值或为最小值， 删除堆顶元素时，先将堆的最后一个元素与堆顶元素交换，由于此时堆的性质被破坏，需对此时的根结点进行向下调整操作。 对堆进行插入操作时，先将新结点放在堆的末端，再对这个新结点执行向上调整操作。 向上调整堆的算法：

<span style="font-size:18px;">void AdjustUp(ElemType A[],int k){
    //参数K为向上调整的结点，也为堆的元素个数
    A[0]=A[k];//A[0]暂存
    int i=k/2;//若结点值大于双亲结点，则将双亲结点向下滑，并继续向上比较
    while(i>0&&A[i]<A[0]){
        A[k]=A[i];//双亲结点下滑
        k=i;
        i=k/2;//继续向上比较
    }//while
    A[k]=A[0];//复制到最终位置
}</span>

如：87,45,78,32,17,65,53，09，63 k=9 A[0]=A[9]=63 i=4 A[4]=32<63 A[9]=A[4]=32 k=4 i=2 A[2]=45<63 A[4]=A[2]=45 k=2 i=1 A[1]=87>63 跳出循环 A[2]=A[0]=63 空间效率：仅使用了常数个辅助单元，所以空间复杂度为O(1). 时间效率：建堆时间为O(n),之后n-1次向下调整，每次调整的时间复杂度为O(h),故在最好、最坏和平均情况下，堆排序的时间复杂度为O(nlog2 n)。 稳定性：在进行筛选时，有可能把后面相同关键字的元素调整到前面，所以堆排序是一种不稳定的排序方法。 如L={1,2,2} len=3 i=1 AdjustDown(A,1,3) k=1, A[0]=A[1]=1 i=2 A[2]=A[3] A[0]>=A[1] 筛选结束 A[1]=A[0]=1 如果严格按照堆排序建立大顶堆，笔者认为是稳定的。但手动建堆，可能将2交换至堆顶——>L={2,1,2}->L={1,2,2} 最终2，2 的次序已经发生变化。