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