複習max heap | Mark's blog
文章推薦指數： 80 %
所以就從 heap 開始。
這次實作的是 max heap ，定義如下圖所示， max heap 為一個完整二元樹(complete binary ...
0%
最近想複習基本的資料結構，首先第一個想到還給老師就是heap了。
所以就從heap開始。
這次實作的是maxheap，定義如下圖所示，maxheap為一個完整二元樹(completebinarytree)，且每個父節點皆大於等於其左右子節點，由於完整二元樹的性質，maxheap資料結構可以很方便的使用陣列來表示。
假設陣列indexi從1開始，heap用陣列來表示又可以延伸出以下節點間的性質：
有了以上的節點性質，就可以很方便的應用在以下的實作。
首先介紹maxheap裡面最重要的部分maxheapify，給定一個元素的index，由top-down的方式遞迴檢查該節點及其左右子節點有無符合maxheap定義，若無則調整之。
程式碼如下：
12345678910111213defmax_heapify(a,i,heap_size):left_i=2*i+1right_i=2*i+2ifleft_i
延伸文章資訊
- 1[資料結構] 堆積(Heap) - iT 邦幫忙
堆積(Heap)，是一種特殊的完全二元樹，而堆疊不一樣，是完全不同的概念。 有分兩種，一種是最小堆積，另一種是最大堆積。 最小堆積. 如下圖，完全二元樹所有的父節點都 ...
- 2資料結構大便當： Binary Heap
如果是max-heap 的話，每個node 都要比自己child 大，如果是min-heap 反之（下圖是max-heap）; （max-heap）root 就會是整個heap 的最大值. （m...
- 3heap
Heap. 定義：堆積分成Min heap與Max heap兩種。Min heap必須具備. 的條件：. (1) 是一棵complete binary tree。 (2) 是一棵min tree...
- 4最大堆積樹中刪除節點最小 - 第一章資料庫概念
【定義】最小-最大堆積樹(Min-Max Heaps Tree)是一個完整二元樹。此二元樹是交替的階層方式呈現，分別為最小階層( min level ) 和最大階層( max level ) ，...
- 5一起幫忙解決難題，拯救IT 人的一天
在特定的應用中，才會明確的說使用的是min heap還是max heap，當兩者皆可時，通常直接以heap來描述。 如果直接把heap當作一棵樹，定義一個heap中的節點高度為某一個節點由 ...
