【資料結構】heap 堆積 介紹
最後更新日期：2024年10月24日
heap 在英文是堆積的意思，
另外，記憶體也有一個叫 heap 區的記憶體，
但他們完全是不同的概念。
heap 是一種完全二元樹(Complete Binary Tree)，代表每一個節點(node)最多只能有兩個子節點(children)，且每層的節點都一定填滿兩個節點，除了最後一層的節點可能只有一個，並且會由左往右新增節點。
特性:
- 滿足堆積排序(Heap Sort)
種類
最大堆積(Max heap)
特性:
- 每個節點的值都大於等於其子節點
- 根節點的值最大
應用:
- 優先隊列(priority queues)(當你需要頻繁獲取或刪除最大元素時)
- 最大堆積在每次插入或刪除元素時，都會調整 heap 的結構以保持 heap 的性質
最小堆積(Min heap)
特性:
- 每個節點的值都小於等於其子節點
- 根節點的值最小
應用:
- 需要頻繁獲取最小元素的應用，如 Dijkstra 算法中的最短路徑求解
操作
插入(insert)
把新元素插入到堆積的最後一個位置，然後向上調整它的位置。
時間複雜度為 O(log n)，其中 n 是堆中的元素個數。
刪除(delete)
- 刪除最大/最小根節點
- 將最後一個節點移到根節點
- 比較子節點，調整位置
時間複雜度為 O(log n)，其中 n 是堆中的元素個數。
堆積排序演算法 (Heap Sort)
利用最大堆或最小堆進行排序。對於最大堆，每次刪除根節點（最大值），並將其與最後一個元素交換，然後重新調整堆的結構。重複這個過程直到整個堆排序完成。
時間複雜度為 O(n log n)，是比較排序中的一種有效方法。
堆積化 Heapify
將一個無序數組轉換為一個 Heap 的過程。
時間複雜度為 O(n)，比逐個插入元素構建堆積更有效率。
向上堆積 Heapify up
當插入一個新元素後，檢查是否需要將其上浮以保持 Heap 的性質。
向下堆積 Heapify down
當刪除根節點後，將最後一個元素移至根節點，並檢查是否需要將其下沉以保持堆積的性質。
應用場景
優先隊列：使用 heap 實現可以使插入和刪除操作的效率大大提高堆排序：利用 heap 進行排序，保證了 O(n log n) 的時間複雜度圖算法：例如 Dijkstra 最短路徑算法和 Prim 最小生成樹算法，都依賴於 heap 結構來快速選擇最小（或最大）值
實作
Heap 一般會透過陣列來實作。
Heap 的高效操作和簡單結構使它在許多需要快速選擇最大或最小元素的場景中非常有用。
