13518219792
本篇文章為大家展示了JavaScript中怎么實現一個二叉堆，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。
專注于為中小企業提供成都網站設計、網站制作服務,電腦端+手機端+微信端的三站合一,更高效的管理,為中小企業大武口免費做網站提供優質的服務。我們立足成都，凝聚了一批互聯網行業人才，有力地推動了1000多家企業的穩健成長，幫助中小企業通過網站建設實現規模擴充和轉變。
前言
二叉樹(Binary Tree)是一種樹形結構，它的特點是每個節點最多只有兩個分支節點，一棵二叉樹通常由根節點、分支節點、葉子節點組成，如下圖所示。每個分支節點也常常被稱作為一棵子樹，而二叉堆是一種特殊的樹，它屬于完全二叉樹。
二叉樹與二叉堆的關系
在日常工作中會遇到很多數組的操作，比如排序等。那么理解二叉堆的實現對以后的開發效率會有所提升，下面就簡單介紹一下什么是二叉樹，什么是二叉堆。
二叉樹特征
根節點：二叉樹最頂層的節點
分支節點：除了根節點以外且擁有葉子節點
葉子節點：除了自身，沒有其他子節點
在二叉樹中，我們常常還會用父節點和子節點來描述，比如上圖中左側節點 2 為 6 和 3 的父節點，反之 6 和 3 是 2 子節點。
二叉樹分類
二叉樹分為滿二叉樹(full binary tree)和完全二叉樹(complete binary tree)。
滿二叉樹：一棵深度為 k 且有 2 ^ k - 1個節點的二叉樹稱為滿二叉樹
完全二叉樹：完全二叉樹是指最后一層左邊是滿的，右邊可能滿也可能不滿，然后其余層都是滿的二叉樹稱為完全二叉樹(滿二叉樹也是一種完全二叉樹)
二叉樹結構
從圖中我們可以看出二叉樹是從上到下依次排列下來，可想而知可以用一個數組來表示二叉樹的結構，從下標 index( 0 - 8 ) 從上到下依次排列。
二叉樹左側節點表達式 index * 2 + 1。例如：以根節點為例求左側節點，根節點的下標為0，則左側節點的序數是1 ，對應數組中的值為1
二叉樹右側節點表達式 index * 2 + 2。例如：以根節點為例求右側節點，根節點的下標為0，則右側節點的序數是2 ，對應數組中的值為 8
二叉樹葉子節點表達式 序數 >= floor( N / 2 )都是葉子節點(N是數組的長度)。例如：floor( 9 / 2 ) = 4 ，則從下標 4 開始的值都為葉子節點
二叉堆特征
二叉堆是一個完全二叉樹，父節點與子節點要保持固定的序關系，并且每個節點的左子樹和右子樹都是一個二叉堆。
從上圖可以看出
圖一：每個父節點大于子節點或等于子節點，滿足二叉堆的性質
圖二：其中有一個父節點小于子節點則不滿足二叉堆性質
二叉堆分類
二叉堆根據排序不同，可以分為最大堆和最小堆
最大堆：根節點的鍵值是所有堆節點鍵值中最大者，且每個父節點的值都比子節點的值大
最小堆：根節點的鍵值是所有堆節點鍵值中最小者，且每個父節點的值都比子節點的值小
如何實現二叉堆
通過上面的講述想必大家對二叉堆有了一定的理解，那么接下來就是如何實現。以最大堆為例，首先要初始化數組然后通過交換位置形成最大堆。
初始化二叉堆
從上面描述，我們可以知道二叉堆其實就是一個數組，那么初始化就非常簡單了。
class Heap{ constructor(arr){ this.data = [...arr]; this.size = this.data.length; } }父子節點交換位置
圖一中 2 作為父節點小于子節點，很顯然不符合最大堆性質。maxHeapify 函數可以把每個不符合最大堆性質的節點調換位置，從而滿足最大堆性質的數組。
調整步驟：
調整分支節點 2 的位置(不滿足最大堆性質)
獲取父節點 2 的左右節點 ( 12 , 5 ) ，從 ( 2 , 15 , 5 ) 中進行比較
找出最大的節點與父節點進行交換，如果該節點本身為最大節點則停止操作
重復 step2 的操作，從 2 , 4 , 7 中找出最大值與 2 做交換(遞歸)
maxHeapify(i) { let max = i; if(i >= this.size){ return; } // 當前序號的左節點 const l = i * 2 + 1; // 當前需要的右節點 const r = i * 2 + 2; // 求當前節點與其左右節點三者中的最大值 if(l < this.size && this.data[l] > this.data[max]){ max = l; } if(r < this.size && this.data[r] > this.data[max]){ max = r; } // 最終max節點是其本身,則已經滿足最大堆性質，停止操作 if(max === i) { return; } // 父節點與最大值節點做交換 const t = this.data[i]; this.data[i] = this.data[max]; this.data[max] = t; // 遞歸向下繼續執行 return this.maxHeapify(max); }形成最大堆
我們可以看到，初始化是由一個數組組成，以下圖為例很顯然并不會滿足最大堆的性質，上述 maxHeapify 函數只是對某一個節點作出對調，無法對整個數組進行重構，所以我們要依次對數組進行遞歸重構。
找到所有分支節點 Math.floor( N / 2 )(不包括葉子節點)
將找到的子節點進行 maxHeapify 操作
rebuildHeap(){ // 葉子節點 const L = Math.floor(this.size / 2); for(let i = L - 1; i >= 0; i--){ this.maxHeapify(i); } }生成一個升序的數組
swap 函數交換首位位置
將最后一個從堆中拿出相當于 size - 1
執行 maxHeapify 函數進行根節點比較找出最大值進行交換
最終 data 會變成一個升序的數組
sort() { for(let i = this.size - 1; i > 0; i--){ swap(this.data, 0, i); this.size--; this.maxHeapify(0); } }插入方法
Insert 函數作為插入節點函數，首先
鴻蒙官方戰略合作共建——HarmonyOS技術社區
往 data 結尾插入節點
因為節點追加，size + 1
因為一個父節點擁有 2 個子節點，我們可以根據這個性質通過 isHeap 函數獲取第一個葉子節點，可以通過第一個葉子節點獲取新插入的節點，然后進行 3 個值的對比，找出最大值，判斷插入的節點。如果跟父節點相同則不進行重構(相等滿足二叉堆性質)，否則進行 rebuildHeap 重構堆
isHeap() { const L = Math.floor(this.size / 2); for (let i = L - 1; i >= 0; i--) { const l = this.data[left(i)] || Number.MIN_SAFE_INTEGER; const r = this.data[right(i)] || Number.MIN_SAFE_INTEGER; const max = Math.max(this.data[i], l, r); if (max !== this.data[i]) { return false; } return true; } } insert(key) { this.data[this.size] = key; this.size++ if (this.isHeap()) { return; } this.rebuildHeap(); }刪除方法
delete 函數作為刪除節點，首先
刪除傳入index的節點
因為節點刪除，size - 1
重復上面插入節點的操作
delete(index) { if (index >= this.size) { return; } this.data.splice(index, 1); this.size--; if (this.isHeap()) { return; } this.rebuildHeap(); }完整代碼
/** * 最大堆 */ function left(i) { return (i * 2) + 1; } function right(i) { return (i * 2) + 2; } function swap(A, i, j) { const t = A[i]; A[i] = A[j]; A[j] = t; } class Heap { constructor(arr) { this.data = [...arr]; this.size = this.data.length; this.rebuildHeap = this.rebuildHeap.bind(this); this.isHeap = this.isHeap.bind(this); this.sort = this.sort.bind(this); this.insert = this.insert.bind(this); this.delete = this.delete.bind(this); this.maxHeapify = this.maxHeapify.bind(this); } /** * 重構堆，形成最大堆 */ rebuildHeap() { const L = Math.floor(this.size / 2); for (let i = L - 1; i >= 0; i--) { this.maxHeapify(i); } } isHeap() { const L = Math.floor(this.size / 2); for (let i = L - 1; i >= 0; i--) { const l = this.data[left(i)] || Number.MIN_SAFE_INTEGER; const r = this.data[right(i)] || Number.MIN_SAFE_INTEGER; const max = Math.max(this.data[i], l, r); if (max !== this.data[i]) { return false; } return true; } } sort() { for (let i = this.size - 1; i > 0; i--) { swap(this.data, 0, i); this.size--; this.maxHeapify(0); } } insert(key) { this.data[this.size++] = key; if (this.isHeap()) { return; } this.rebuildHeap(); } delete(index) { if (index >= this.size) { return; } this.data.splice(index, 1); this.size--; if (this.isHeap()) { return; } this.rebuildHeap(); } /** * 交換父子節點位置，符合最大堆特征 * @param {*} i */ maxHeapify(i) { let max = i; if (i >= this.size) { return; } // 求左右節點中較大的序號 const l = left(i); const r = right(i); if (l < this.size && this.data[l] > this.data[max]) { max = l; } if (r < this.size && this.data[r] > this.data[max]) { max = r; } // 如果當前節點最大，已經是最大堆 if (max === i) { return; } swap(this.data, i, max); // 遞歸向下繼續執行 return this.maxHeapify(max); } } module.exports = Heap;示例
相信通過上面的講述大家對最大堆的實現已經有了一定的理解，我們可以利用這個來進行排序。
const arr = [15, 12, 8, 2, 5, 2, 3, 4, 7]; const fun = new Heap(arr); fun.rebuildHeap(); // 形成最大堆的結構 fun.sort();// 通過排序，生成一個升序的數組 console.log(fun.data) // [2, 2, 3, 4, 5, 7, 8, 12, 15]
上述內容就是JavaScript中怎么實現一個二叉堆，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注創新互聯行業資訊頻道。
