sort_heap 对完全二叉树排序

pop_heap和sort_heap操作的对象是max-heap,即父节点比子节点大的heap结构。

push_heap是将使插入新元素后仍满足max-heap结构(原来也是max-heap结构)。

make_heap是讲一段数据转化为max-heap.

因为每次pop_heap可获得heap中键值最大的元素,所以可持续对整个heap做pop_heap操作,每次将操作范围从后向前缩减一个元素,便可实现一个递增序列。

// 以下這個 sort_heap() 不允許指定「大小比較標準」
template <class RandomAccessIterator>
void sort_heap(RandomAccessIterator first, RandomAccessIterator last) {
  // 以下,每執行一次 pop_heap(),極值(在STL heap中為極大值)即被放在尾端。
  // 扣除尾端再執行一次 pop_heap(),次極值又被放在新尾端。一直下去,最後即得
  // 排序結果。
  while (last - first > 1)
     pop_heap(first, last--); // 每執行 pop_heap() 一次,操作範圍即退縮一格。
}
原文地址:https://www.cnblogs.com/helloweworld/p/2846250.html