四、
（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, 计算父节点、左儿子、右儿子的下标
-
inline
int
Parent(
int
i) {
return
i>>1; }
-
inline
int
Left(
int
i) {
return
i<<1; }
-
inline
int
Right(
int
i) {
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>
-
using
namespace
std;
-
-
-
// 根据某节点下标i, 计算父节点、左儿子、右儿子的下标
-
inline
int
Parent(
int
i) {
return
i>>1; }
-
inline
int
Left(
int
i) {
return
i<<1; }
-
inline
int
Right(
int
i) {
return
(i<<1)|1; }
//位运算乘2后,结果是偶数所以最后一位一定是0, 所以|1将会把最后一位变成1，从而实现加1的效果
-
-
-
inline
void
Swap(
int
&a,
int
&b) {
if
(a!=b){a^=b; b^=a; a^=b;} }
-
-
-
/*
-
堆排序的基本过程函数：
-
-
MaxHeap(A,len,i): 其运行时间为O(lgN),是保持最大堆性质的关键
-
BuidMaxHeap(A): 过程，以线性时间运行，可以在无需的输入数组基础上构造出最大堆
-
HeapSort(A): 对一个数组原地进行排序
-
-
*/
-
-
// 保持堆的性质，使以i为根的子树成为最大堆
-
void
MaxHeap(
int
*A,
int
heap_size,
int
i){
-
-
int
l,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将整个数组变成一个最大堆
-
void
BuidMaxHeap(
int
*A,
int
heap_size){
-
-
for
(
int
i=heap_size>>1; i>=1; –i){
-
MaxHeap(A,heap_size,i);
-
}
-
}
-
-
// 堆排序
-
void
HeapSort(
int
*A,
int
heap_size){
-
-
BuidMaxHeap(A,heap_size);
-
int
len=heap_size;
-
for
(
int
i=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++实现：
-
// 优先级队列
-
-
int
HeapMaxNum(
int
*A){
-
return
A[1];
-
}
-
-
int
HeapExtractMax(
int
*A,
int
heap_size){
-
if
(heap_size>=1){
-
int
max=A[1];
-
A[1] = A[heap_size];
-
–heap_size;
-
MaxHeap(A,heap_size,1);
-
return
max;
-
}
-
}
-
-
bool
HeapIncreaseKey(
int
*A,
int
i,
int
key){
-
if
(key<A[i])
-
return
false
;
-
A[i] = key;
-
while
(i>1 && A[Parent(i)]<A[i]){
-
Swap(A[i],A[Parent(i)]);
-
i = Parent(i);
-
}
-
return
true
;
-
}
-
-
void
MaxHeapInsert(
int
*A,
int
key,
int
heap_size){
-
++heap_size;
-
A[heap_size] = -2147484646;
-
HeapIncreaseKey(A,heap_size,key);
-
}
—— 生命的意义，在于赋予它意义。