heap堆
STL中的堆默认是最大堆,想用最小堆的话,必须在push_heap, pop_heap,make_heap等每一个函数后面加第三个参数greater<int>(),括号不能省略。
heap堆的方法
- make_heap(_First, _Last):使序列变成堆。默认是建立最大堆的。
- push_heap(_First, _Last):新添加一个元素在末尾,然后重新调整堆序。该算法必须是在一个已经满足堆序的条件下,添加元素。
- pop_heap(_First, _Last):与push_heap类似,参数一样。把堆顶元素取出来,重新调整堆序。
- sort_heap(_First, _Last):每次pop_heap可以获得堆中最大的元素,那么我们持续对整个heap做pop_heap操作,每次将操作的范围向前缩减一个元素。当整个程序执行完毕后,我们得到一个非降的序列。