JavaScript中怎么實現一個二叉堆

本篇文章為大家展示了JavaScript中怎么實現一個二叉堆，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。

前言

二叉樹(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 函數作為插入節點函數，首先

1. 鴻蒙官方戰略合作共建——HarmonyOS技術社區

2. 往 data 結尾插入節點

3. 因為節點追加，size + 1

4. 因為一個父節點擁有 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中怎么實現一個二叉堆，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。