順序容器（幕後英雄） — 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.