【算法导论】排序 （二）：堆排序

四、（1）堆排序

第一次听堆排序是在107lab听忠哥讲的，但是没讲怎么实现。那时刚看了数据结构的二叉树，还以为要通过指针建立二叉树的方式来实现，觉得挺难的。

其实堆排序实现没有想象中的那么难。

“堆”这个词最初是在堆排序中提出来的，但后来就逐渐指”废料收集储存区“，就像程序设计语言Lisp和Java中所提供的设施那样。我们这里的堆数据结构不是废料收集存储区。

堆排序的运行时间与归并排序一样为O(n lg n), 但是一种原地（in place）排序。

（二叉）堆数据结构是一种数组对象，它可以被视为一棵完全二叉树。

对于一个数组arr[ ]={16,14,10,8,7,9,3,2,4,1}的存储数据结构如下图：

在这个结构中，对于每一个根节点i ，要保证它都比他的子节点大

我们可以用一个数组A【1...length【A】】来表示这个完全二叉树结构。 其中A【1】为根节点1

首先问题是求父节点、左儿子、右儿子的坐标，通过观察我们可以用宏或者内联函数实现：

//根据某节点下标i,计算父节点、左儿子、右儿子的下标
inlineintParent(inti){returni>>1;}
inlineintLeft(inti){returni<<1;}
inlineintRight(inti){return(i<<1)|1;}//位运算乘2后,结果是偶数所以最后一位一定是0,所以|1将会把最后一位变成1，从而实现加1的效果

无论是《C++ primer》还是《Effective C++》，都讲过宏的缺陷，用内联函数是个更好的选择。位运算做乘除的速度更快。

至于算法演示过程在《算法导论》上讲得很详细，不再赘述。

堆排序过程需要以下三个函数：

1、Max-Heapify(A,i): 保持堆的性质,让A【i】在最大堆中“下降”，使以i节点为根的字数成为最大树

2、Buid-Max-Heap(A)：自底向上将数组A【1...n】变成一个最大堆

3、Heap-Sort（A）： 进行堆排序

C++代码实现：（数组A是下标1开始的）

/*算法导论第6章堆排序*/
#include<cstdio>
#include<algorithm>
usingnamespacestd;


//根据某节点下标i,计算父节点、左儿子、右儿子的下标
inlineintParent(inti){returni>>1;}
inlineintLeft(inti){returni<<1;}
inlineintRight(inti){return(i<<1)|1;}//位运算乘2后,结果是偶数所以最后一位一定是0,所以|1将会把最后一位变成1，从而实现加1的效果


inlinevoidSwap(int&a,int&b){if(a!=b){a^=b;b^=a;a^=b;}}


/*
堆排序的基本过程函数：

MaxHeap(A,len,i):其运行时间为O(lgN),是保持最大堆性质的关键
BuidMaxHeap(A):过程，以线性时间运行，可以在无需的输入数组基础上构造出最大堆
HeapSort(A):对一个数组原地进行排序

*/

//保持堆的性质，使以i为根的子树成为最大堆
voidMaxHeap(int*A,intheap_size,inti){

intl,r,max;
l=Left(i);
r=Right(i);

if(l<=heap_size&&A[l]>A[i])
max=l;
else
max=i;

if(r<=heap_size&&A[r]>A[max])
max=r;

if(max!=i){
Swap(A[i],A[max]);
MaxHeap(A,heap_size,max);
}
}

//建堆，自底向上用MaxHeap将整个数组变成一个最大堆
voidBuidMaxHeap(int*A,intheap_size){

for(inti=heap_size>>1;i>=1;--i){
MaxHeap(A,heap_size,i);
}
}

//堆排序
voidHeapSort(int*A,intheap_size){

BuidMaxHeap(A,heap_size);
intlen=heap_size;
for(inti=heap_size;i>=2;--i){
Swap(A[1],A[i]);
--len;
MaxHeap(A,len,1);
}
}

（2）优先级队列

C++ STL中的priority_queue就是用这种方法来实现的。

1、Heap-MaxiNum（A）： 取出堆中的最大值

2、Heap-Extract-Max（A）：删除堆中的最大值并返回它的值

3、Heap-Increase-Key（A，i，key）：将节点i的值增加到key，这里key要比i节点原来的数大。

4、Max-Heap-Insert(A, key): 插入一个新元素key到堆中，要用到3的函数

C++实现：

//优先级队列

intHeapMaxNum(int*A){
returnA[1];
}

intHeapExtractMax(int*A,intheap_size){
if(heap_size>=1){
intmax=A[1];
A[1]=A[heap_size];
--heap_size;
MaxHeap(A,heap_size,1);
returnmax;
}
}

boolHeapIncreaseKey(int*A,inti,intkey){
if(key<A[i])
returnfalse;
A[i]=key;
while(i>1&&A[Parent(i)]<A[i]){
Swap(A[i],A[Parent(i)]);
i=Parent(i);
}
returntrue;
}

voidMaxHeapInsert(int*A,intkey,intheap_size){
++heap_size;
A[heap_size]=-2147484646;
HeapIncreaseKey(A,heap_size,key);
}

—— 生命的意义，在于赋予它意义。

原创http://blog.csdn.net/shuangde800，By D_Double