資料結構- 堆積(Heap)

堆積

堆積(Heap)，是一棵二元樹，樹根(Root)的鍵值會大於(或小於)等於子樹的鍵值，當根節點的值小於等於子節點的值，此堆積稱為最小堆積(Min Heap)；反之，當根節點的值大於等於子節點的值，此堆積稱為最大堆積(Max Heap)

與二元搜尋樹(Binary Search Tree)最大的差異是，Heap不管左子樹與右子樹的大小，但是二元搜尋樹中右子樹鍵值會大於左子樹所有鍵值

下圖就是最大堆積，最上方稱為根節點(Root)，每個節點最多可以擁有兩個節點

如何將一棵二元樹調整成Heap？

以最大堆積為例

1. 樹根與左、右子節點相比，若樹根比左、右子節點大，不用交換；反之，則要交換

2. 先讓樹根(Root)的左、右子節點先比較，找出子節點的最大，再與父節點相比。 此種調整方式優勢為父節點與子節點只會交換一次，大多數以此種方式調整。Heap只要父節點大於等於子節點即可，左、右子節點之間的大小則不予理會

時間複雜度

特性

• 每個節點最多只有兩個節點

• 堆積是一棵完全樹，除了最底層，其他層節點都會被填滿，最底層盡可能由左至右新增資料

• 資料會從最下層開始新增資料，若資料該層已經滿了，則往下產生新的一層並追加資料

• Heap不管左子樹與右子樹的大小

參考資料：

• 堆積

• 《演算法圖鑑》第一章：資料結構

• 用 Heap 實作 Priority Queue