STL源码分析-heap部分

heap部分属于序列式容器一章

但是heap并不属于STL容器组件，其帮助于priority queue.

priority queue运行用户用任何次序将任何元素推入容器内，但取出时一定是从数值最高的元素开始取，binary max heap具有这样的特性，适合作为priority queue.底层机制。

若使用list作为priority queue底层机制，元素的插入操作可享常数时间，但是要找到list中的极值，要对整个list遍历。时间过长。

binary heap就是一种完全二叉树。也就是整颗树除了最底层的叶节点之外，是填满的，比如如下：

array表达式：ABCDEFGHIJ

由于完全二叉树 内没有任何节点漏洞，这带来一个极大的好处：可以利用array来存储所有节点。

也就是说某个节点位于array的i处时，左子节点位于2i处，右子节点位于2i+1处，父节点位于i/2处。通过这种简单的位置规则，array可以轻易实现出完全二叉树。这种利用array

表述tree的方式，成为隐式表述法

但array的缺点是无法动态改变大小，而heap却需要，因此用vector代替array是更好的选择

heap分为max-heap和min-heap两种，前者每个节点的键值大于等于其子节点键值，也就是从大到小排列，后者则是从小到大。因此max-heap的最大值在根节点，并总是位于底层vector的起头处。STL提供的是max-heap。因此只对max-heap进行分析。

heap算法

push_heap算法

功能：插入一个新元素

为了满足完全二叉树的条件，新加入的元素一定要放在最下一层作为叶节点，并填补在由左至右的第一个空格，也就是插入在vector的end()处。然后为了满足max-heap的条件，也就是每个节点大于等于其子节点的键值，执行一个上溯（percolate up）程序：将新节点与父节点比较，若比父节点大，就对换位置，如此一致上溯，知道不需对换或者根节点为止。

pop_heap算法

功能：将最大值取走

最大值必然在根节点，pop操作取走根节点（其实是摄至底部容器vector的尾端节点）后，为了满足完全二叉树，必须割舍最下层最右边的叶节点，并将其值重新安插至max-heap。

执行下溯程序：将空间节点与其较大子节点对调，并持续下放直到叶节点为止，然后将割舍的元素值设给这个已到达叶层的空洞节点，再执行一次上溯程序，即可。

sort_heap算法

功能：将heap排序，由小到大

既然每次pop_heap可获得heap键值最大的元素，如果持续对heap执行pop操作，能够得到一个递增序列。因为pop_heap会将最大元素放在最尾端。因此是递增序列。

注意：排序过后，原来的heap不是一个合法的heap了。

make_heap算法

功能：将现有的数据转化为一个heap，主要依据就是完全二叉树的隐式表述。

在实际程序中，要对一个vector(int) A进行排序，可以利用make_heap先将A转化为一个合法的heap，然后利用sort_heap将heap进行从小到大排序即可：

vector<int> A;        
make_heap(A.begin(), A.end());
sort_heap(A.begin(), A.end());