[FGISC。Nanro] 未來開端

Heap呢，有些地方翻做「錐型結構」或「錐疊」，電腦辭典譯作「堆積」，聽起來跟堆疊有點像，而且也可以用陣列來實做，但是對heap來說，他是一種樹狀的結構(且必須是完整二元樹)，而不是堆疊那樣純粹的線性結構。

而基本上heap分成兩種，一種是min-heap，另一種即是max-heap而他的特色，便是「任一節點，其值恆小/大於子節點」，且如此一來，root永遠是所有之中最小/最大的一個。
 (下面我們用min-heap當做講解範例)

基本上，完整二元樹就是一棵由上到下，由左到右編號的樹
像這個：

　　　　　　　１
                    ／ ＼
　　　　　２　　 ３
              ／ ＼　  ／  ＼
　　　４　　５ ６　　７
因為root的編號是1，而每個節點n的父節點(parent)一定是(n/2)，子節點(child)一定是(2*n)和(2*n+1)
所以基本上，我們可以利用陣列的編號特性來直接實做heap。
附帶一提，我們在使用完整二元樹時，通常不會用到[0]的那格，而直接從[1]開始用，如此能完整地合乎完整二元樹的編號及其父子節點之間的運算關係，heap的使用亦同。

至於為什麼不用在其他的二元樹？是因為如果出現了
                           １
                     ／
                   ２
               ／
           ３
       ／
   ４
  這樣子的二元樹，第十個節點所在的位置就是2的9次方(512)，而會留有許多的空節點
  這種情況我們稱之為「稀疏」，而較常使用鏈結串列來實做。而完整二元樹則不會
  有這樣子的情形。

所謂的向上調整呢，就是將一個節點與他的父節點(parent)比較，如果小於父節點便與其交換，利用遞迴一直往上做上述判斷，直到大於其父節點或是已換成root為止。

而向下調整則是與其較小的子節點比較，如果大於較小的子節點，那麼便與他交換，同樣使用遞迴，往下確認直到該節點皆小於其子節點或為樹葉為止。

總而言之，無論是向上調整或是向下調整，皆是讓一個元素移動到他該在的位置，而讓heap保持在合法狀態的一種操作。

對於heap這種資料結構，我們有[插入insert]與[刪除delete]兩種基本操作。

[插入]
    當我們新增一個元素時，會將它放置到目前heap的最後一個位置
   (以陣列來說，原本有N個元素，那麼就是加到N+1個位置去)
   再對其做調整。

[刪除]
   而在min-heap之中，取出最小值即是取出root，而取出後我們可以執行刪除root的動作。
   當我們刪除掉root時，便將最後一個元素移到root的位置。
   (以陣列來說，原本有N個元素，便是將那第N個移到第1個的位置)
   再對其做調整。

heap的建立方式有兩種，一種是每次將每個元素插入之後，邊做向上調整；另一種則是一次讀入所有的元素放入陣列，從最後一個元素開始對其做向下調整。這兩種方法前者較慢，但可以保證過程中heap皆為合法狀態；後者較快，但是當資料讀完之前，heap還無法使用，因為它還不是一個完整的heap。

ACM Q10954 Add All
這題簡單的來說，就是每次要相加的，皆為目前數列中最小的兩個元素(加完之後便丟進去變成新元素)。我們可以先把輸入的元素做成heap，然後每次皆先取出最小的(相當於從heap中刪除)，把最後一個元素丟到root的位置然後進行向下調整，再把剛剛取出的那個元素與root相加，此時root的值變動了，有可能不符合heap的合法狀態，故我們得再做一次向下調整，以此類推，直到節點只剩下1個。

另外，上述題目也可以單純只使用向上調整，也就是每次有變動，便把新資料重新做成heap。然而在處理過程中，每次不合法的節點只有至多一個，所以全部再跑一次這樣的做法非常地耗時。
(解該題：純向上調整－1.600秒；向上+向下－0.030秒)

順帶一提，對所有的元素進行向上調整，我們稱之為重建(Rebuild)，而正常的heap在建完之後並不會再用到建立，所以其實沒有這種操作。

除了上述的兩種作法之外，這題也可以只用向下調整，也就是建樹用向下，然後如上面所提向下+向上的方法，取出一次root之後做向下，然後把它加到調整完的新root再對其做向下調整。