如何用 JS 實現(xiàn)二叉堆

作者：北淵 2021-03-02 10:57:39

二叉樹(Binary Tree)是一種樹形結構，它的特點是每個節(jié)點最多只有兩個分支節(jié)點，一棵二叉樹通常由根節(jié)點、分支節(jié)點、葉子節(jié)點組成，如下圖所示。每個分支節(jié)點也常常被稱作為一棵子樹，而二叉堆是一種特殊的樹，它屬于完全二叉樹。

[[384564]]

前言

二叉樹與二叉堆的關系

在日常工作中會遇到很多數(shù)組的操作，比如排序等。那么理解二叉堆的實現(xiàn)對以后的開發(fā)效率會有所提升，下面就簡單介紹一下什么是二叉樹，什么是二叉堆。

二叉樹特征

根節(jié)點：二叉樹最頂層的節(jié)點
分支節(jié)點：除了根節(jié)點以外且擁有葉子節(jié)點
葉子節(jié)點：除了自身，沒有其他子節(jié)點

在二叉樹中，我們常常還會用父節(jié)點和子節(jié)點來描述，比如上圖中左側節(jié)點 2 為 6 和 3 的父節(jié)點，反之 6 和 3 是 2 子節(jié)點。

二叉樹分類

二叉樹分為滿二叉樹(full binary tree)和完全二叉樹(complete binary tree)。

滿二叉樹：一棵深度為 k 且有 2 ^ k - 1個節(jié)點的二叉樹稱為滿二叉樹
完全二叉樹：完全二叉樹是指最后一層左邊是滿的，右邊可能滿也可能不滿，然后其余層都是滿的二叉樹稱為完全二叉樹(滿二叉樹也是一種完全二叉樹)

二叉樹結構

從圖中我們可以看出二叉樹是從上到下依次排列下來，可想而知可以用一個數(shù)組來表示二叉樹的結構，從下標 index( 0 - 8 ) 從上到下依次排列。

二叉樹左側節(jié)點表達式 index * 2 + 1。例如：以根節(jié)點為例求左側節(jié)點，根節(jié)點的下標為0，則左側節(jié)點的序數(shù)是1 ，對應數(shù)組中的值為1
二叉樹右側節(jié)點表達式 index * 2 + 2。例如：以根節(jié)點為例求右側節(jié)點，根節(jié)點的下標為0，則右側節(jié)點的序數(shù)是2 ，對應數(shù)組中的值為 8
二叉樹葉子節(jié)點表達式序數(shù) >= floor( N / 2 )都是葉子節(jié)點(N是數(shù)組的長度)。例如：floor( 9 / 2 ) = 4 ，則從下標 4 開始的值都為葉子節(jié)點

二叉堆特征

二叉堆是一個完全二叉樹，父節(jié)點與子節(jié)點要保持固定的序關系，并且每個節(jié)點的左子樹和右子樹都是一個二叉堆。

從上圖可以看出

圖一：每個父節(jié)點大于子節(jié)點或等于子節(jié)點，滿足二叉堆的性質
圖二：其中有一個父節(jié)點小于子節(jié)點則不滿足二叉堆性質

二叉堆分類

二叉堆根據(jù)排序不同，可以分為最大堆和最小堆

最大堆：根節(jié)點的鍵值是所有堆節(jié)點鍵值中最大者，且每個父節(jié)點的值都比子節(jié)點的值大
最小堆：根節(jié)點的鍵值是所有堆節(jié)點鍵值中最小者，且每個父節(jié)點的值都比子節(jié)點的值小

如何實現(xiàn)二叉堆

通過上面的講述想必大家對二叉堆有了一定的理解，那么接下來就是如何實現(xiàn)。以最大堆為例，首先要初始化數(shù)組然后通過交換位置形成最大堆。

初始化二叉堆

從上面描述，我們可以知道二叉堆其實就是一個數(shù)組，那么初始化就非常簡單了。

class Heap{ 
  constructor(arr){ 
    this.data = [...arr]; 
    this.size = this.data.length; 
  } 
}

父子節(jié)點交換位置

圖一中 2 作為父節(jié)點小于子節(jié)點，很顯然不符合最大堆性質。maxHeapify 函數(shù)可以把每個不符合最大堆性質的節(jié)點調換位置，從而滿足最大堆性質的數(shù)組。

調整步驟：

調整分支節(jié)點 2 的位置(不滿足最大堆性質)
獲取父節(jié)點 2 的左右節(jié)點 ( 12 , 5 ) ，從 ( 2 , 15 , 5 ) 中進行比較
找出最大的節(jié)點與父節(jié)點進行交換，如果該節(jié)點本身為最大節(jié)點則停止操作
重復 step2 的操作，從 2 , 4 , 7 中找出最大值與 2 做交換(遞歸)

maxHeapify(i) { 
  let max = i; 
 
  if(i >= this.size){ 
    return; 
  } 
  // 當前序號的左節(jié)點 
  const l = i * 2 + 1; 
  // 當前需要的右節(jié)點 
  const r = i * 2 + 2; 
 
  // 求當前節(jié)點與其左右節(jié)點三者中的最大值 
  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é)點是其本身,則已經(jīng)滿足最大堆性質，停止操作 
  if(max === i) { 
    return; 
  } 
 
  // 父節(jié)點與最大值節(jié)點做交換 
  const t = this.data[i]; 
  this.data[i] = this.data[max]; 
  this.data[max] = t; 
 
  // 遞歸向下繼續(xù)執(zhí)行 
  return this.maxHeapify(max); 
}

形成最大堆

我們可以看到，初始化是由一個數(shù)組組成，以下圖為例很顯然并不會滿足最大堆的性質，上述 maxHeapify 函數(shù)只是對某一個節(jié)點作出對調，無法對整個數(shù)組進行重構，所以我們要依次對數(shù)組進行遞歸重構。

找到所有分支節(jié)點 Math.floor( N / 2 )(不包括葉子節(jié)點)
將找到的子節(jié)點進行 maxHeapify 操作

rebuildHeap(){ 
  // 葉子節(jié)點 
  const L = Math.floor(this.size / 2); 
  for(let i = L - 1; i >= 0; i--){ 
    this.maxHeapify(i); 
  } 
}

生成一個升序的數(shù)組

swap 函數(shù)交換首位位置
將最后一個從堆中拿出相當于 size - 1
執(zhí)行 maxHeapify 函數(shù)進行根節(jié)點比較找出最大值進行交換
最終 data 會變成一個升序的數(shù)組

sort() { 
  for(let i = this.size - 1; i > 0; i--){ 
    swap(this.data, 0, i); 
    this.size--; 
    this.maxHeapify(0); 
  } 
}

插入方法

Insert 函數(shù)作為插入節(jié)點函數(shù)，首先

往 data 結尾插入節(jié)點
因為節(jié)點追加，size + 1
因為一個父節(jié)點擁有 2 個子節(jié)點，我們可以根據(jù)這個性質通過 isHeap 函數(shù)獲取第一個葉子節(jié)點，可以通過第一個葉子節(jié)點獲取新插入的節(jié)點，然后進行 3 個值的對比，找出最大值，判斷插入的節(jié)點。如果跟父節(jié)點相同則不進行重構(相等滿足二叉堆性質)，否則進行 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 函數(shù)作為刪除節(jié)點，首先

刪除傳入index的節(jié)點
因為節(jié)點刪除，size - 1
重復上面插入節(jié)點的操作

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(); 
  } 
 
  /** 
   * 交換父子節(jié)點位置，符合最大堆特征 
   * @param {*} i 
   */ 
  maxHeapify(i) { 
    let max = i; 
 
    if (i >= this.size) { 
      return; 
    } 
 
    // 求左右節(jié)點中較大的序號 
    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; 
    } 
 
    // 如果當前節(jié)點最大，已經(jīng)是最大堆 
    if (max === i) { 
      return; 
    } 
 
    swap(this.data, i, max); 
 
    // 遞歸向下繼續(xù)執(zhí)行 
    return this.maxHeapify(max); 
  } 
} 
 
module.exports = Heap;

示例

相信通過上面的講述大家對最大堆的實現(xiàn)已經(jīng)有了一定的理解，我們可以利用這個來進行排序。

const arr = [15, 12, 8, 2, 5, 2, 3, 4, 7]; 
const fun = new Heap(arr); 
fun.rebuildHeap(); // 形成最大堆的結構 
fun.sort();// 通過排序，生成一個升序的數(shù)組 
console.log(fun.data) // [2, 2, 3, 4, 5, 7, 8, 12, 15]

總結

文章中主要講述了二叉樹、二叉堆的概念，然后通過代碼實現(xiàn)二叉堆。我們可以通過二叉堆來做排序和優(yōu)先級隊列等。

責任編輯：未麗燕來源： ZooTeam Blog

二叉樹二叉堆節(jié)點