JavaScript中怎么實(shí)現(xiàn)一個(gè)二叉堆

本篇文章為大家展示了JavaScript中怎么實(shí)現(xiàn)一個(gè)二叉堆，內(nèi)容簡(jiǎn)明扼要并且容易理解，絕對(duì)能使你眼前一亮，通過(guò)這篇文章的詳細(xì)介紹希望你能有所收獲。

前言

二叉樹(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)也常常被稱(chēng)作為一棵子樹(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ù)分為滿(mǎn)二叉樹(shù)(full binary tree)和完全二叉樹(shù)(complete binary tree)。

• 滿(mǎn)二叉樹(shù)：一棵深度為 k 且有 2 ^ k - 1個(gè)節(jié)點(diǎn)的二叉樹(shù)稱(chēng)為滿(mǎn)二叉樹(shù)

• 完全二叉樹(shù)：完全二叉樹(shù)是指最后一層左邊是滿(mǎn)的，右邊可能滿(mǎn)也可能不滿(mǎn)，然后其余層都是滿(mǎn)的二叉樹(shù)稱(chēng)為完全二叉樹(shù)(滿(mǎn)二叉樹(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)，滿(mǎn)足二叉堆的性質(zhì)

• 圖二：其中有一個(gè)父節(jié)點(diǎn)小于子節(jié)點(diǎn)則不滿(mǎ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)換位置，從而滿(mǎn)足最大堆性質(zhì)的數(shù)組。

調(diào)整步驟：

• 調(diào)整分支節(jié)點(diǎn) 2 的位置(不滿(mǎn)足最大堆性質(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)滿(mǎn)足最大堆性質(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ì)滿(mǎn)足最大堆的性質(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ù)，首先

1. 鴻蒙官方戰(zhàn)略合作共建——HarmonyOS技術(shù)社區(qū)

2. 往 data 結(jié)尾插入節(jié)點(diǎn)

3. 因?yàn)楣?jié)點(diǎn)追加，size + 1

4. 因?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)(相等滿(mǎn)足二叉堆性質(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)注億速云行業(yè)資訊頻道。