簡介
概念
堆是一種比較特殊的資料結構，它用陣列實作的二叉樹，并且總是滿足以下性質：
- 堆總是一棵完全二叉樹
- 堆中某個結點總是不大于或不小于其父結點的的值
屬性
堆分為兩種：根結點最大的堆叫作最大堆或大根堆；根結點最小的堆叫作最小堆或小根堆，
堆屬性非常有用，其使得堆常常被當做優先佇列使用，因為可以快速地訪問到“最重要”的元素，
堆和二叉搜索樹的區別
堆并不能取代二叉搜索樹，它們之間有相似之處也有一些不同，兩者的主要區別如下：
| 屬性 | 堆 | 二叉搜索樹 |
|---|---|---|
| 結點的順序 | 在最小堆中父結點必須比子結點小，在最大堆中父結點必須比子結點大，變化是從上到下 |
左子結點比父結點小，父結點比右子結點小，變化是從左到右 |
| 記憶體占用 | 使用陣列作為底層存盤結構，占用記憶體空間較小 | 使用鏈表作為底層存盤結構，占用記憶體空間較大 |
| 平衡 | 不需要整棵樹有序 | 必須是平衡的，總體上是有序的 |
| 搜索 | 搜索很慢 | 搜索很快 |
堆的實作
存盤
實作一個堆，首先是涉及到如何存盤一個堆，
根據堆總是一棵完全二叉樹的性質，以及完全二叉樹比較適合用陣列來存盤的概念，可以知道用陣列存盤堆是比較好的選擇，
從上圖可以看到，陣列中下標為 i 的結點的左子結點，就是下標為 2i 的結點，右子結點就是下標為 2i + 1 的結點，父結點就是下標為 i/2 的結點，
堆化
往堆中插入或者洗掉一個元素后，重要的是需要繼續滿足堆的兩個特性，而這個重新滿足堆特性的程序稱為堆化，
堆化實際上有兩種：從下往上、從上往下，
插入元素
插入元素時涉及的是從下往上的堆化方法，
往堆中插入一個元素其實就是往底層陣列的末尾添加元素，下面是示例圖：
從下往上堆化的程序比較簡單，實際上就是將插入的元素與父結點進行比較，出現不符合特性的情況就互換兩個結點，一直重復這個程序，直至父子結點之間滿足堆的特性，
洗掉元素
從堆的特性可以看出，堆頂元素存盤的就是堆中資料的最大值或最小值，
當洗掉堆頂元素的時候，為保持堆的特性，則會涉及到從上往下的堆化方法，
從上往下堆化不是直接從堆頂元素開始與子結點進行互換，而是先將陣列中的最后一個元素移到被洗掉結點位置（為了滿足完全二叉樹的特性），然后利用同樣的父子結點比對方法，
通常，對于大根堆會比較較大的子結點，對于小根堆會比較較小的子結點，出現不符合特性的情況就互換兩個結點，一直重復這個程序，直至父子結點之間滿足堆的特性，
這種方法堆化之后的結果，肯定滿足完全二叉樹的特性，
復雜度
一個包含 n 個節點的完全二叉樹，樹的高度不會超過 \(\log_2n\)，
堆化的程序是順著節點所在路徑比較交換的，所以堆化的時間復雜度跟樹的高度成正比，也就是 \(O(\log n)\)，
插入資料和洗掉堆頂元素的主要邏輯就是堆化，所以往堆中插入一個元素和洗掉堆頂元素的時間復雜度都是 \(O(\log n)\)，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/440406.html
標籤：其他
上一篇：路徑計數動態規劃dp題目