[資結] 淺談Heap

Heap呢，有些地方翻做「錐型結構」或「錐疊」，電腦辭典譯作「堆積」，聽起來跟堆疊有點 ... Heap的用途很廣，也有很多奇怪的用途，這裡就不多提囉～. [FGISC。

Nanro]未來開端 跳到主文 耕耘未來 部落格全站分類：社團組織 相簿 部落格 留言 名片 Feb09Sat200800:04 [資結]淺談Heap ＊什麼是Heap？Heap呢，有些地方翻做「錐型結構」或「錐疊」，電腦辭典譯作「堆積」，聽起來跟堆疊有點像，而且也可以用陣列來實做，但是對heap來說，他是一種樹狀的結構(且必須是完整二元樹)，而不是堆疊那樣純粹的線性結構。

而基本上heap分成兩種，一種是min-heap，另一種即是max-heap而他的特色，便是「任一節點，其值恆小/大於子節點」，且如此一來，root永遠是所有之中最小/最大的一個。

 (下面我們用min-heap當做講解範例)＊談Heap之前，先談談完整二元樹……基本上，完整二元樹就是一棵由上到下，由左到右編號的樹像這個：　　　　　　　１              ／＼　　　　　２　　３           ／＼　 ／ ＼　　　４　　５６　　７因為root的編號是1，而每個節點n的父節點(parent)一定是(n/2)，子節點(child)一定是(2*n)和(2*n+1)所以基本上，我們可以利用陣列的編號特性來直接實做heap。

附帶一提，我們在使用完整二元樹時，通常不會用到[0]的那格，而直接從[1]開始用，如此能完整地合乎完整二元樹的編號及其父子節點之間的運算關係，heap的使用亦同。

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

而完整二元樹則不會 有這樣子的情形。

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

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

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

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

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

[刪除]  而在min-heap之中，取出最小值即是取出root，而取出後我們可以執行刪除root的動作。

  當我們刪除掉root時，便將最後一個元素移到root的位置。

  (以陣列來說，原本有N個元素，便是將那第N個移到第1個的位置)  再對其做調整。

 ＊如何建立heap？heap的建立方式有兩種，一種是每次將每個元素插入之後，邊做向上調整；另一種則是一次讀入所有的元素放入陣列，從最後一個元素開始對其做向下調整。

這兩種方法前者較慢，但可以保證過程中heap皆為合法狀態；後者較快，但是當資料讀完之前，heap還無法使用，因為它還不是一個完整的heap。

＊簡單的例題ACMQ10954AddAll這題簡單的來說，就是每次要相加的，皆為目前數列中最小的兩個元素(加完之後便丟進去變成新元素)。

我們可以先把輸入的元素做成heap，然後每次皆先取出最小的(相當於從heap中刪除)，把最後一個元素丟到root的位置然後進行向下調整，再把剛剛取出的那個元素與root相加，此時root的值變動了，有可能不符合heap的合法狀態，故我們得再做一次向下調整，以此類推，直到節點只剩下1個。

另外，上述題目也可以單純只使用向上調整，也就是每次有變動，便把新資料重新做成heap。

然而在處理過程中，每次不合法的節點只有至多一個，所以全部再跑一次這樣的做法非常地耗時。

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

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

Heap的用途很廣，也有很多奇怪的用途，這裡就不多提囉～大概是這樣，後面的應用應該很複雜XD另外，網路上有個模擬max-heap操作過程的頁面，相當不錯，可以去看看:)http://mis.im.tku.edu.tw/~tweety15c/Heap/Heap.html 全站熱搜 創作者介紹 aikosenoo [FGISC。

Nanro]未來開端 aikosenoo發表在痞客邦留言(1)人氣() E-mail轉寄 全站分類：不設分類個人分類：初識‧資料結構此分類上一篇：[資結]UnionSet 此分類下一篇：[鏈結串列]ACM#540 上一篇：[暴力]ACM#381中譯+解析 下一篇：[程設]質數篩法 歷史上的今天 2009:[C++]初學筆記(2) ▲top 留言列表 發表留言 Search Articles Collection Collection 2010七月(1) 2009六月(1) 2009二月(2) 2009一月(4) 2008二月(12) 2007九月(7) 2007八月(18) 1990二月(1) 所有文章列表 Category 未來開端(1) 未來開端(5) 解題相關(8) 初心之章(10)初識‧資料結構(4)中階雜項(9)演算法其壹‧廣度與深度優先搜尋(4)演算法其貳‧動態規劃法(2)演算法其參‧排序與搜尋(1)演算法其肆‧圖形演算法(2)別類‧中譯題目(2) 程式語言(4) C(1)C++(2)Java(0)PHP(0) WebDesign(1) CSS(2) 其他雜項(0)未分類文章(2) Links ACM相關網站 UvaOnlineJudgeLucky貓的ACM園地FGISCLuckyCat鏡像WorldofSevenElectronicBoardACMOnlineJudge(舊站) 程式設計與演算法 DJWS的網路日誌C++程式設計常見程式演算筆記 其他相關 北一女中資訊科網站Anny'sComputerScienceWebNPSC補完計畫Celia's HotArticles Comments Counter 本日人氣： 累積人氣： QRCode 回到頁首 回到主文 免費註冊 客服中心 痞客邦首頁 ©2003-2022PIXNET 關閉視窗