大家好，我是小丞同學，一名大二的前端愛好者
這篇文章将講解資料結構中的堆
非常感謝你的閱讀，不對的地方歡迎指正
願你忠于自己，熱愛生活
歡迎大家關注本專欄，持續關注最新文章~
本專欄的其他内容
從這裡開始 【化解資料結構】從這裡開啟資料結構和算法
棧 【化解資料結構】什麼是棧？手寫實作一個棧結構!
隊列 【化解資料結構】詳解隊列，優先隊列，循環隊列，并實作一個隊列
集合 【化解資料結構】詳解集合結構，并實作一個集合
字典 【化解資料結構】詳解字典結構，并實作一個字典
樹 【化解資料結構】詳解樹結構，并實作二叉搜尋樹
知識點搶先看
什麼是堆？
如何實作一個堆結構？
手寫實作一個堆結構
LeetCode 實戰
碎碎念
在上一篇文章中，我們學習了樹結構，它是一個非順序結構，接下來我們再來學習一個非順序結構堆
一、什麼是堆結構？
你可能會知道在記憶體中有棧和堆之分，但是這裡堆和記憶體中的堆不一樣，這裡的堆是一種資料存儲的方式
堆實際上是一種特殊的隊列：優先隊列，關于優先隊列在隊列文章中已經有講過。也就是隊列中有很多待執行的任務，執行時會根據優先級來執行，優先級高的會先被執行
這也可以很容易了解，比如醫院急診室裡就有對病患的優先級之分，醫生會優先處理病情嚴重的患者，再處理相較弱的患者
對于堆而言它是一種抽象的資料結構，或者說邏輯上的資料結構，并不是實體上真實存在的資料結構
在這裡我們主要讨論的是二叉堆這種最常見的結構，它是用一棵完全二叉樹來實作的
對于二叉樹，我們在上一篇也有涉及，它是采用數組來實作的
是以二叉堆實際也是使用數組來實作的
那麼什麼是完全二叉樹呢？
完全二叉樹和滿二叉樹又類似，我們先來看看什麼是滿二叉樹
1. 滿二叉樹
樹中除了葉子節點，每個節點都有兩個子節點
一個二叉樹，如果每一個層的結點數都達到最大值，則這個二叉樹就是滿二叉樹。也就是說，如果一個二叉樹的層數為K，且結點總數是(2^k) -1 ，則它就是滿二叉樹。
是以對于滿二叉樹的節點而言，它的度要麼是 0，要麼是 2，也就是要麼有 2 個子節點，要麼是葉子節點
如圖就是一個滿二叉樹
2. 完全二叉樹
在滿二叉樹的性質上，最後一層的葉子節點，均在左樹上
若設二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層所有的結點都連續集中在最左邊，這就是完全二叉樹。
如圖一棵完全二叉樹
它們的差別：
完全二叉樹最後一層沒有滿
滿二叉樹一定是完全二叉樹
完全二叉樹不一定是滿二叉樹
3. 堆的特點
好了了解了什麼是完全二叉樹，那堆有什麼特點呢？
堆是一棵完全二叉樹
任意節點都優于它的所有子節點
如果任意節點都大于它的所有子節點，那麼它叫做最大堆，也叫大頂堆
如果任意節點都小于它的所有子節點，那麼它叫做最小堆，也叫小頂堆
左邊是一個最大堆，所有的子節點都小于父節點
二、如何能夠實作一個堆結構呢？
在 JS 中通過數組來實作一個堆結構，其實本質就是一個數組。在上一篇文章結尾也說了，無論什麼資料結構，在記憶體中都隻是數組，或者對象罷了，所有的資料結構都是我們心中存在的，我們知道這麼做的好處是怎麼怎麼樣
在這裡選用數組來實作一個堆
利用廣度優先周遊，将樹填入數組裡，這樣我們就能用一個數組來表示一個堆了
小秘訣
左側子節點在數組中的位置是 2 * index + 1
右側子節點在數組中的位置是 2 * index + 2
父節點的位置是 (index - 1) / 2
是以我們不僅能夠使用數組來表示一個堆，我們還能擷取任意一個節點在數組中的位置，接下來我們就實作一個最小堆
三、堆中有哪些方法？
我們給堆添加一些方法，一遍它在插入時，能插到準确的位置，删除時，其他的元素也能進行合理的移動
方法 含義
swap() 交換兩個數
getParentIndex(i) 擷取 i 的父節點
getLeftIndex(i) 擷取 i 的左子節點
getRightIndex(i) 擷取 i 的右子節點
shirtUp(i) 上移操作
shirtDown(i) 下移操作
insert(value) 插入值
pop() 删除堆頂
peek() 擷取堆頂
size() 擷取堆的大小
四、手寫實作一個最小堆
在前面我們已經知道了最小堆的定義，它的所有節點都小于等于它的子節點，是以我們根據這個特性，以及3個小秘訣來實作一個最小堆
1. 建立一個 MinHeap 類
利用數組來實作一個堆類
class MinHeap {
constructor() {
this.heap = []
}
} 2. 實作 swap 方法
我們需要維護一個堆結構，在元素插入删除的時候，常常需要進行位置的變化，是以我們需要通過交換位置來實作
封裝一個 swap 方法，接收交換位置的兩個節點
swap(i1, i2) {
const temp = this.heap[i1]
[this.heap[i1], this.heap[i2]] = [this.heap[i2], temp]
} 在這裡采用數組解構的方式來指派，看着舒服一點
3. 實作 getParentIndex 方法
getParentIndex 方法擷取某個節點父元素在數組中的位置
根據上面的小秘訣：父節點的位置是 (index - 1) / 2
在這裡我們采用二進制的方式來取值
小課堂：你知道 JavaScript 中的 ~~ 運算符是什麼意思嗎
getParentIndex(i) {
// 取商 （i- 1）/2 等同于 Math.floor((i-1)/2)
// 二進制數向右邊移一位，這樣剛好就是求商
return (i - 1) >> 1
} 4. 實作 getLeftIndex 方法
同樣的根據秘訣：左側子節點在數組中的位置是 2 * index + 1
getLeftIndex(i) {
return i * 2 + 1
} 5. 實作 getRightIndex 方法
getRightIndex(i) {
return i * 2 + 2
} 6. 實作 shirtUp 方法
這個方法是實作最小堆的關鍵之一，在我們插入元素時，需要對元素進行判斷，我們需要将插入的元素移到符合它的位置
如何實作呢？采用遞歸
首先我們需要先判斷節點的位置是否在堆的頂部，這也是遞歸結束的标記之一
接下來進行遞歸體的内容，我們遞歸實作的目的是通過交換使元素到達合适位置
是以判斷插入元素和父節點的值關系，如果父節點的值大于目前節點值，則進行上移（因為最小堆，小的在堆頂）
直至遞歸結束
shirtUp(index) {
// 如果在堆頂，停止上移
if(index == 0) return
// 擷取父元素
const parentIndex = this.getParentIndex(index)
// 比較
if (this.heap[parentIndex] > this.heap[index]) {
// 交換
this.swap(parentIndex, index)
// 遞歸
this.shirtUp(parentIndex)
}
} 7. 實作 insert方法
在寫好了上移 shirtUp 方法，我們就可以實作 insert 方法來看看我們實作的效果了
insert 方法的作用是插入一個元素，在堆中插入一個元素之後，我們需要通過 shirtUp 方法來将這個元素移到合适的位置，這個操作留給 shirtUp 方法來解決
注意哦，shirtUp 方法接收的是 index ，也就是索引值
insert(value) {
this.heap.push(value)
this.shirtUp(this.heap.length - 1)
} 來看看在一個堆中插入元素是如何運作的吧，這是一個最大堆中的動圖，最小堆也一樣
時間複雜度是多少你知道嗎？ O(logK)
8. 實作 pop 方法
為什麼需要有下移的方法，當我們直接删除堆頂時，會導緻整個堆的結構的變化，使得大小關系轉變，難以操作
是以我們在删除堆頂時，隻需要用數組尾部的元素，替換堆頂元素，這樣改變的就隻有首尾兩個元素，我們再對堆頂進行下移判斷，這樣通過不斷地交換，就能實作最小堆
pop() {
// 用最後一個替換堆頂
this.heap[0] = this.heap.pop()
// 再下移
this.shirtDown(0)
} 9. 實作 shirtDown 方法
接下來我們實作最為關鍵的下移代碼，如何實作呢？
和左右子節點進行比較
左子節點小于目前節點，交換，繼續遞歸
右子節點小于目前節點，交換，遞歸
shirtDown(index) {
const leftIndex = this.getLeftIndex(index)
const rightIndex = this.getRightIndex(index)
// 左側子節點小于目前節點
if (this.heap[leftIndex] < this.heap[index]) {
this.swap(leftIndex, index)
this.shirtDown(leftIndex)
}
// 右側子節點小于目前節點
if (this.heap[rightIndex] < this.heap[index]) {
this.swap(rightIndex, index)
this.shirtDown(rightIndex)
}
} 我們來看看删除堆頂時會發生什麼？
10. 實作 peek 方法
傳回堆頂元素，也就是堆的最小值，數組的第一位
peek() {
return this.heap[0]
} 11. 實作 size 方法
最後，實作最簡單的方法，通過數組的 length 來擷取即可
size() {
return this.heap.length
} 12. 完整的 MinHeap 類
// 寫一個最小堆
class MinHeap {
constructor() {
this.heap = []
}
// 擷取父節點
getParentIndex(i) {
// 取商 （i- 1）/2 等同于 Math.floor((i-1)/2)
// 二進制數向右邊移一位，這樣剛好就是求商
return (i - 1) >> 1
}
// 擷取左節點
getLeftIndex(i) {
return i * 2 + 1
}
getRightIndex(i) {
return i * 2 + 2
}
// 交換兩個數的方法
swap(i1, i2) {
const temp = this.heap[i1]
[this.heap[i1], this.heap[i2]] = [this.heap[i2], temp]
}
// 上移操作，最小堆，小的要在最上面
shirtUp(index) {
// 如果在堆頂，停止上移
if (index == 0) return
const parentIndex = this.getParentIndex(index)
if (this.heap[parentIndex] > this.heap[index]) {
this.swap(parentIndex, index)
this.shirtUp(parentIndex)
}
}
// 下移操作
shirtDown(index) {
const leftIndex = this.getLeftIndex(index)
const rightIndex = this.getRightIndex(index)
// 左側子節點小于目前節點
if (this.heap[leftIndex] < this.heap[index]) {
this.swap(leftIndex, index)
this.shirtDown(leftIndex)
}
// 右側子節點小于目前節點
if (this.heap[rightIndex] < this.heap[index]) {
this.swap(rightIndex, index)
this.shirtDown(rightIndex)
}
}
// 插入 O(logK)
insert(value) {
this.heap.push(value)
this.shirtUp(this.heap.length - 1)
}
// 删除堆頂
pop() {
// 用最後一個替換堆頂
this.heap[0] = this.heap.pop()
// 再下移
this.shirtDown(0)
}
// 擷取堆頂
peek() {
return this.heap[0]
}
// 擷取大小
size() {
return this.heap.length
}
} 五、LeetCode 實戰
在前端世界中，堆也有它的應用場景，它能夠高效的找到最大值，最小值，時間複雜度為 O(1)，
利用堆結構，我們可以輕松解決找出最大、最小元素、第 K 大元素登問題，但遠不止于這些
幾道 LeetCode 中關于堆的題目