[資料結構] Heap 的概念與實作 - 資工學習筆記

Heap是一種資料結構，使用一維陣列來儲存在理解上可以把他想成是一顆tree 而heap有兩個property: Heap property: min-heap: root必為最小的值 ... 2016年8月10日星期三 [資料結構]Heap的概念與實作 Heap是一種資料結構，使用一維陣列來儲存 在理解上可以把他想成是一顆tree 而heap有兩個property: Heapproperty:  min-heap:root必為最小的值 max-heap:root必為最大的值 Shapeproperty:由左至右，每層都填滿 因為擁有這樣的特性，heap可以快速的拿到最大或最小值，因此也可以拿來做sorting--Heapsort，時間複雜度是O(nlogn) 概念： 圖片來源：https://en.wikipedia.org/wiki/Heap_(data_structure) 上圖是max-heap的範例，也就是說root永遠是最大值。

如：100>19和36，19>17和3等。

而在實作時是用陣列的方式儲存，依序是：100,19,36,17,3,25,1,2,7。

以下將分成insert及delete說明。

Insert: 由於heap一定是由左到右依序填滿，因此我們可以將要insert進來的node先放在整個tree的最後面，再慢慢地與root交換，直到符合heap的要求。

以上圖為例，假設我們現在要insert一個新的node，值是30，則我們先將其放在3的下面，當成3的子節點，再往上看他的root。

發現30>3，則交換。

再往上看，發現30>19，則再交換，接著再往上看，發現30<100，於是停止。

Delete 刪除的時候也是一樣，當我們拿掉root的時候，先將整個陣列的最後一個值放上來，再做調整。

以上圖為例，假如我們要刪掉36這個node，則將7移到36的位置，再往下看他的子節點，發現25>7則跟25交換，接著再看右節點，發現25>1，所以停止。

張貼者： 柚子 於 清晨6:09 以電子郵件傳送這篇文章BlogThis！分享至Twitter分享至Facebook分享到Pinterest 標籤： 資料結構 沒有留言: 張貼留言 較新的文章 較舊的文章 首頁 訂閱： 張貼留言(Atom) 標籤 多媒體 資料結構 電腦相關素材網站 Ajax AndroidStudio API ChromeExtension Docker Git Groovy&Grails Web XMPP 網誌存檔 ►  2017 (1) ►  二月 (1) ▼  2016 (8) ►  十二月 (1) ▼  八月 (2) [資料結構]Heap的概念與實作 [Heroku]將NodeJS部署到Heroku上 ►  六月 (1) ►  四月 (2) ►  二月 (2) ►  2015 (17) ►  十二月 (2) ►  九月 (2) ►  六月 (1) ►  五月 (4) ►  四月 (8) 相關網站 XDite'sBlog 搞笑談軟工