STL中heap相关函数

heap并不是属于STL中的containers，而是在<algorithm>下提供了相关的函数make_heap，sort_heap，pop_heap，push_heap

函数的说明：

make_heap(_First, _Last, _Comp)

默认是建立最大堆的。对int类型，可以在第三个参数传入greater<int>() 得到最小堆，传入less<int>() 得到最大堆。

max-heap是优先队列（priority queue）的底层实现机制

max-heap实际上的实现可以是以一个vector表现的完全二叉树（complete binary tree）

Comp可以没有，那就是默认的maxheap

void make_heap (RandomAccessIterator first, RandomAccessIterator last);

first、last是两个随机的迭代器

// range heap example
#include <iostream>     // std::cout
#include <algorithm>    // std::make_heap, std::pop_heap, std::push_heap, std::sort_heap
#include <vector>       // std::vector

int main () {
  int myints[] = {10,20,30,5,15};
  std::vector<int> v(myints,myints+5);

  std::make_heap (v.begin(),v.end());
  std::cout << "initial max heap   : " << v.front() << '\n';

  std::pop_heap (v.begin(),v.end()); v.pop_back();
  std::cout << "max heap after pop : " << v.front() << '\n';

  v.push_back(99); std::push_heap (v.begin(),v.end());
  std::cout << "max heap after push: " << v.front() << '\n';

  std::sort_heap (v.begin(),v.end());

  std::cout << "final sorted range :";
  for (unsigned i=0; i<v.size(); i++)
    std::cout << ' ' << v[i];

  std::cout << '\n';

  return 0;
}

/*
Output:
initial max heap   : 30
max heap after pop : 20
max heap after push: 99
final sorted range : 5 10 15 20 99
*/

对于其它的heap函数，参数类型相同；

push_heap()：把元素添加在底层vector的end()处，然后重新调整堆序（可以是执行一个siftup()函数）；

pop_heap()：把堆顶元素取出来，放到了数组或者是vector的末尾，用原来末尾元素去替代，然后end迭代器减1（后常跟vector的pop_back()操作），执行siftdown()下溯函数来重新调整堆序；

sort_heap()：持续对整个heap做pop_heap操作，每次将操作的范围向前缩减一个元素，则可以得到排序好的序列。由于maxheap的top放在end处，所以sort_heap完之后顺序输出是非降序；

如上的算法需要在堆上进行操作