顺序容器（幕后英雄） — heap

heap不属于stl容器，它扮演者priority queue的助手。heap是一种完全二叉树，可由数组来实现，但heap需要动态改变大小，所以最终选择了vector作为底层容器。stl默认提供最大堆。

题外话：分析heap的源码就能清楚的理解堆这种数据结构的例程，而stl库代码的质量又很高，所以看堆的代码，stl源码是一个很好的选择。

为了满足完全二叉树的性质，新插入的元素一定最后一个叶子节点，也就是容器尾端，再然后再进行上滤操作，让新元素找到正确的位置。以push_heap为例：

<code>template</code> <code>&lt;</code><code>class</code> <code>randomaccessiterator&gt; </code><code>// 新元素已插入容器尾部</code>

<code>inline</code> <code>void</code> <code>push_heap(randomaccessiterator first, randomaccessiterator last) {</code>

<code>  </code><code>__push_heap_aux(first, last, distance_type(first), value_type(first));</code>

<code>}</code>

<code></code>

这个函数已经假设新插入元素已经位于vector的尾端，所以last指向新元素之后的一个位置。distance_type和value_type都是通过特性萃取机（iterator_traits）提取迭代器的相应类型：difference_type和value_type。提取过程如下：

<code>template</code> <code>&lt;</code><code>class</code> <code>iterator&gt;</code>

<code>inline</code> <code>typename</code> <code>iterator_traits&lt;iterator&gt;::difference_type*</code>

<code>distance_type(</code><code>const</code> <code>iterator&amp;) {  </code><code>// 决定迭代器difference_type</code>

<code>  </code><code>return</code> <code>static_cast</code><code>&lt;</code><code>typename</code> <code>iterator_traits&lt;iterator&gt;::difference_type*&gt;(0);</code>

<code>inline</code> <code>typename</code> <code>iterator_traits&lt;iterator&gt;::value_type*</code>

<code>value_type(</code><code>const</code> <code>iterator&amp;) { </code><code>// 决定迭代器value_type</code>

<code>  </code><code>return</code> <code>static_cast</code><code>&lt;</code><code>typename</code> <code>iterator_traits&lt;iterator&gt;::value_type*&gt;(0);</code>

注意，这里使用了static_cast把0进行了转换，由于我们是需要迭代器所内嵌的类型，而不关心具体值，所以用0来代替是ok的。

push_heap内部调用函数__push_heap_aux，代码如下：

<code>template</code> <code>&lt;</code><code>class</code> <code>randomaccessiterator, </code><code>class</code> <code>distance, </code><code>class</code> <code>t&gt;</code>

<code>inline</code> <code>void</code> <code>__push_heap_aux(randomaccessiterator first,</code>

<code>                            </code><code>randomaccessiterator last, distance*, t*) {</code>

<code>  </code><code>__push_heap(first, distance((last - first) - 1), distance(0), </code>

<code>              </code><code>t(*(last - 1)));  </code><code>// 新插入元素值</code>

最后两个参数只有类型名，没有参数名，印证了前面的说法。这个函数内部又调用了一个__push_heap函数，这个函数做了实际的上滤操作。在看__push_heap的源码之前，先分析一下它的四个参数：

first：迭代器，指向容器开头。

distance((last - first) - 1)：last - first - 1是新插入元素的下标值，这里用了一个c风格的类型转换，符合泛型思想。

distance(0)：根元素的下标值，同样进行了类型转换。

t(*(last - 1))：新插入元素的元素值，是上滤操比较操作的基础。

下面是核心代码：

<code>void</code> <code>__push_heap(randomaccessiterator first, distance holeindex,</code>

<code>                 </code><code>distance topindex, t value) {</code>

<code>  </code><code>distance parent = (holeindex - 1) / 2;  </code><code>// 父节点下标</code>

<code>  </code><code>while</code> <code>(holeindex &gt; topindex &amp;&amp; *(first + parent) &lt; value) { </code><code>// value为新插入元素值</code>

<code>    </code><code>*(first + holeindex) = *(first + parent);</code>

<code>    </code><code>holeindex = parent;             </code><code>// 上移</code>

<code>    </code><code>parent = (holeindex - 1) / 2;   </code><code>// 上移</code>

<code>  </code><code>}    </code>

<code>  </code><code>*(first + holeindex) = value;</code>

sgi stl的heap，元素是从vector的下标0开始排的，知道了这一点，看这段代码就很轻松了。

参考：

《stl源码剖析》 p172.