分类： C/C++
2014-06-22 18:18:47
堆并不是STL的组件，但是经常充当着底层实现结构。比如优先级队列（Priority Queue）等等。
堆是一种完全二叉树，因此我们可以用数组来存储所有节点。在这里的实现中，采用了一个技巧：将数组中索引为0的元素保留，设置为极大值或者为极小值（依据大顶堆或者小顶堆而定）。那么当某个节点的索引是i时，其左子节点索引为2*i，右子节点索引为2*i+1.父节点是i/2（这里/表示高斯符号，取整）。这种以数组表示树的方式，我们成为隐式表述法（implicit reprentation）。我们这里用C++ STL中的容器vector实现替代数组的功能。
堆分为大顶堆和小顶堆。这里介绍并实现的是大顶堆。
此操作是向堆中添加一个节点。为了满足完全二叉树的条件，新加入的元素一定放在最下面的一层作为叶节点，并填补在由左至右的第一个空格，在这里放在底层容器vector的end()处。
很显然，新元素的加入很可能使得堆不在满足大顶堆的性质---每个节点的键值都大于或等于其子节点的键值。为了调整使得其重新满足大顶堆的特点，在这里执行一个上溯（percolate up）操作：将新节点与父节点比较，如果其键值比父节点大，就交换父子的位置，如此一直上溯，直到不需要交换或者到根节点为止。
此操作取走根节点。对于大顶堆，取得的是堆中值最大的节点，对于小顶堆，取得的是堆中值最小的节点。STL实现并不是将这个节点直接删除，而是将其放在底层容器vector的尾端。而原尾端的节点插入到前面的适当位置。
我们首先保存原vector尾端的节点值，然后将根节点值存储在此处。为了实将原尾端节点的值插入适当位置，重新构建大顶堆，我们实施如下调整堆的操作：
先执行下溯（percolate down）操作：从根节点开始将空洞节点（一开始是根节点）和较大子节点交换，并持续向下进行，直到到达叶节点为止。然后将已保存的原容器vector尾端节点赋给这个已到达叶层的空洞节点。
注意，到这里并没有结束。因为这时候可能还没有满足大顶堆的特性。还需要执行一次上溯操作。这样，便重新构建了大顶堆。
此操作是依据已有的各元素构建堆。
其中，各元素已经存放在底层容器vector中。
构建堆实质是一个不断调整堆（即前面pop_heap算法中的调整堆的操作）的过程---通过不断调整子树，使得子树满足堆的特性来使得整个树满足堆的性质。
叶节点显然需要调整，第一个需要执行调整操作的子树的根节点是从后往前的第一个非叶结点。从此节点往前到根节点对每个子树执行调整操作，即可构建堆。
堆排序算法。执行此操作之后，容器vector中的元素按照从小到大的顺序排列。
构建大顶堆之后，不断执行pop_heap算法取出堆顶的元素，即可。因为每次取得的是最大的元素，将其放在容器vector的最尾端。所以到最后vector中的元素是从小到大排列的。
