二叉堆与堆排序

二叉堆是一种优先级队列(priority queue)。搜索树维护了全部数据结构的有序性，而在我们不需要得知全局有序，仅仅需要全局的极值时，这样是一种没有必要的浪费。根据对象的优先级进行访问的方式，称为循优先级访问(call-by-priority)。优先级队列本身并不是一个队列结构，而是根据优先级始终查找并访问优先级最高数据项的数据结构。

首先，定义优先级队列基类。需要支持的操作，主要是插入、获取最大(最小)元素、删除最大(最小)元素。

1 template<typename T> struct PQ
2 {
3     virtual void insert(T) = 0;
4     virtual T getMax() = 0;
5     virtual T delMax() = 0;
6 };

完全二叉堆

最为常用的堆结构，就是完全二叉堆。在逻辑形式上，结构必须完全等同于完全二叉树，同时，堆顶意外的每个节点都不大于（小于）其父亲，即堆有序。

如果堆顶最大，称为最大二叉堆。反之，称为最小二叉堆。

因为完全二叉堆等同于完全二叉树的结构，故高度应当为O(logn)。在前面二叉树的一篇里，提到了完全二叉树的层次遍历结构可以采用向量表示，更加简洁方便、内存上更加紧凑。回顾一下，一个节点的秩为n，它左孩子的秩为2*n+1,右孩子为2*n+2；当n！=0时，n的父亲为[n/2]-1(向上取整)。向量结构对于删除添加等，分摊复杂度为O(1)。

 1 template<typename T> class PQ_ComplHeap: public PQ<T>, public Vector<T>
 2 {
 3 protected:
 4     Rank percolateDown(Rank n, Rank i);//下滤
 5     Rank percolateUp(Rank i);//上滤
 6     void heapify(Rank n);//Floyd建堆算法
 7 public:
 8     PQ_ComplHeap() {};
 9     PQ_ComplHeap(T* A, Rank n) { copyFrom(A, 0, n); heapify(n); }
10     void insert(T);//允许重复故必然成功
11     T getMax();
12     T delMax();
13 };

查询

优先级队列最大的优势所在，始终维持全局最大(最小)值为堆顶。因此只需要返回首元素即可。

1 template<typename T> T PQ_ComplHeap<T>::getMax()
2 {
3     return _elem[0];
4 }

插入

插入操作，首先把新元素加到向量末尾。因为需要维持堆序性，逐层检查是否有序并做出调整，这个过程称为上滤。上滤的高度不超过树高，因此复杂度不超过O(logn)。

 1 template<typename T> void PQ_ComplHeap<T>::insert(T e)
 2 {
 3     Vector<T>::insert(e);//将新词条接到向量末尾
 4     percolateUp(_size - 1);//对该词条进行上滤
 5 }
 6 template<typename T> Rank PQ_ComplHeap<T>::percolateUp(Rank i)
 7 {
 8     while (ParentValid(i))
 9     {
10         Rank j = Parent(i);
11         if (lt(_elem[i], _elem[j])) break;
12         swap(_elem[i], _elem[j]); i = j;//继续向上
13     }
14     return i;//返回上滤最终抵达的位置
15 }

删除

每次删除操作，都将删除堆顶。采用的策略，是把向量末尾的元素补充到堆顶，然后向下逐层比较，维持堆序性，与上滤对应地，称为下滤。

 1 template<typename T> T PQ_ComplHeap<T>::delMax()
 2 {
 3     T maxElem = _elem[0];
 4     _elem[0] = _elem[--_size];//用末尾的值代替
 5     percolateDown(_size, 0);//下滤
 6     return maxElem;//返回备份的最大词条
 7 }
 8 template<typename T> Rank PQ_ComplHeap<T>::percolateDown(Rank n, Rank i)//前n个词条中的第i个进行下滤
 9 {
10     Rank j;
11     while (i!= (j = ProperParent(_elem, n, i)))//i以及两个孩子中，最大的不是i
12     {
13         swap(_elem[i], _elem[j]); i = j;//交换，并向下
14     }
15     return i;//返回下滤到达的位置
16 }

同样，删除操作除下滤外，均只需要常数时间，而下滤复杂度也不超过高度，故同样为O(logn)。

建堆

二叉堆一个重要的问题就是如何建立堆，通常是由一个向量结构进行建堆。最常用的方法有两种，一种是逐个元素插入，然后对每个元素都进行上滤。这样操作的复杂度为O(log1+log2+...+logk)=O(nlogn)。其实，整个过程的复杂度与对全局进行排序相当。

介绍一种更快的建堆方法，Floyd算法。算法核心思想是，把建堆的过程等效于堆的合并操作，即两个堆H1、H2以及节点p的合并操作，此时，如果H1和H2已经符合堆序性，那么只需要把p作为H1、H2的父亲，并对p进行下滤操作即可，最终成为一个完整的堆。

1 template<typename T> void PQ_ComplHeap<T>::heapify(Rank n)//Floyd建堆法
2 {
3     for (int i = LastInternal(n); InHeap(n, i); i--)//自底向上下滤，从最后一个节点的父亲开始
4         percolateDown(n, i);
5 }

仅对内部节点进行下滤即可。操作的复杂度为O(n)。对比可以发现，插入后上滤效率低的来源，是对每个节点都进行了上滤，而Floyd方法对内部节点进行下滤，而完全二叉堆中的外部节点数量多，并且深度小的节点远远少于高度小的节点。

堆排序

堆排序算法其实与选择排序法非常相似。其核心思想都是将序列分为前后两个部分：未排序部分U、已经排序部分S。不同之处仅在于，如何从前半部分选择极值元素。借助堆结构，堆顶即为最值，因此可以很快的选择出想要的元素，并与U部分的末尾交换即可，这也正是delMax（）所做的工作。因为完全二叉堆的该过程不超过O(logn)，所以算法的复杂度为O(nlogn)，比选择排序法的O(n^2)有了很大的提升。