pop_heap是怎么排序的?
这个函数很令人不解,很错乱的一个函数。
[解决办法]
pop_heap算法
此操作取走根节点。对于大顶堆,取得的是堆中值最大的节点,对于小顶堆,取得的是堆中值最小的节点。STL实现并不是将这个节点直接删除,而是将其放在底层容器vector的尾端。而原尾端的节点插入到前面的适当位置。
我们首先保存原vector尾端的节点值,然后将根节点值存储在此处。为了实将原尾端节点的值插入适当位置,重新构建大顶堆,我们实施如下调整堆的操作:
先执行下溯(percolate down)操作:从根节点开始将空洞节点(一开始是根节点)和较大子节点交换,并持续向下进行,直到到达叶节点为止。然后将已保存的原容器vector尾端节点赋给这个已到达叶层的空洞节点。
注意,到这里并没有结束。因为这时候可能还没有满足大顶堆的特性。还需要执行一次上溯操作。这样,便重新构建了大顶堆
[解决办法]
首先弄清楚最大堆的性质:每个节点的数值都比它的孩子中的数值大,这样对一个构建好的最大堆来说,堆中最大的元素在堆顶,就是根节点。
[解决办法]
pop_heap就是拿走堆顶元素,然后进行调整以保证剩余元素依然是一个堆。
它不只是用来排序的,循环调用这个函数直到堆为空才是排序。堆数据还可以用来实现优先队列、获取(最大的)N个元素等。
堆的作用是帮助我们在logN的时间内找到所有元素的最大值,这一特性正好可以实现一个N*LogN的选择排序,也就产生了“堆排序”:
make_heap
while (堆不为空)
pop_heap --》线性表首