摘要：二叉樹(shù)二叉樹(shù)是一種樹(shù)形結(jié)構(gòu)，它的特點(diǎn)是每個(gè)節(jié)點(diǎn)最多只有兩個(gè)分支節(jié)點(diǎn)，一棵二叉樹(shù)通常由根節(jié)點(diǎn)，分支節(jié)點(diǎn)，葉子節(jié)點(diǎ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ù)。

根節(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ù)語(yǔ)
在二叉樹(shù)中，我們常常還會(huì)用父節(jié)點(diǎn)和子節(jié)點(diǎn)來(lái)描述，比如圖中2為6和3的父節(jié)點(diǎn)，反之6和3是2子節(jié)點(diǎn)

在二叉樹(shù)的第i層上，至多有2^i-1個(gè)節(jié)點(diǎn)

i=1時(shí)，只有一個(gè)根節(jié)點(diǎn)，2^(i-1) = 2^0 = 1

深度為k的二叉樹(shù)至多有2^k-1個(gè)節(jié)點(diǎn)

i=2時(shí)，2^k-1 = 2^2 - 1 = 3個(gè)節(jié)點(diǎn)

對(duì)任何一棵二叉樹(shù)T，如果總結(jié)點(diǎn)數(shù)為n0，度為2(子樹(shù)數(shù)目為2)的節(jié)點(diǎn)數(shù)為n2,則n0=n2+1

樹(shù)的節(jié)點(diǎn)個(gè)數(shù)至少為1，而二叉樹(shù)的節(jié)點(diǎn)個(gè)數(shù)可以為0

樹(shù)中節(jié)點(diǎn)的最大度數(shù)(節(jié)點(diǎn)數(shù)量)沒(méi)有限制,而二叉樹(shù)的節(jié)點(diǎn)的最大度數(shù)為2

樹(shù)的節(jié)點(diǎn)沒(méi)有左右之分，而二叉樹(shù)的節(jié)點(diǎn)有左右之分

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

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

完全二叉樹(shù)：完全二叉樹(shù)是指最后一層左邊是滿的，右邊可能滿也可能不滿，然后其余層都是滿的二叉樹(shù)稱為完全二叉樹(shù)(滿二叉樹(shù)也是一種完全二叉樹(shù))

用一個(gè)數(shù)組來(lái)表示二叉樹(shù)的結(jié)構(gòu)，將一組數(shù)組從根節(jié)點(diǎn)開(kāi)始從上到下，從左到右依次填入到一棵完全二叉樹(shù)中，如下圖所示

通過(guò)上圖我們可以分析得到數(shù)組表示的完全二叉樹(shù)擁有以下幾個(gè)性質(zhì)：

left = index * 2 + 1，例如：根節(jié)點(diǎn)的下標(biāo)為0，則左節(jié)點(diǎn)的值為下標(biāo)array[0＊2+1]=1

right = index * 2 + 2，例如：根節(jié)點(diǎn)的下標(biāo)為0，則右節(jié)點(diǎn)的值為下標(biāo)array[0＊2+2]=2

序數(shù) >= floor(N/2)都是葉子節(jié)點(diǎn)，例如：floor(9/2) = 4，則從下標(biāo)4開(kāi)始的值都為葉子節(jié)點(diǎn)

二叉堆由一棵完全二叉樹(shù)來(lái)表示其結(jié)構(gòu)，用一個(gè)數(shù)組來(lái)表示，但一個(gè)二叉堆需要滿足如下性質(zhì)：

二叉堆的父節(jié)點(diǎn)的鍵值總是大于或等于(小于或等于)任何一個(gè)子節(jié)點(diǎn)的鍵值

當(dāng)父節(jié)點(diǎn)的鍵值大于或等于(小于或等于)它的每一個(gè)子節(jié)點(diǎn)的鍵值時(shí)，稱為最大堆（最小堆）

從上圖可以看出：

左圖：父節(jié)點(diǎn)總是大于或等于其子節(jié)點(diǎn)，所以滿足了二叉堆的性質(zhì)，

右圖：分支節(jié)點(diǎn)7作為2和12的父節(jié)點(diǎn)并沒(méi)有滿足其性質(zhì)(大于或等于子節(jié)點(diǎn))。

insert：插入節(jié)點(diǎn)

delete：刪除節(jié)點(diǎn)

max-hepify：調(diào)整分支節(jié)點(diǎn)堆性質(zhì)

rebuildHeap：重新構(gòu)建整個(gè)二叉堆

sort：排序

從上面簡(jiǎn)單的介紹，我們可以知道，一個(gè)二叉堆的初始化非常的簡(jiǎn)單，它就是一個(gè)數(shù)組

初始化一個(gè)數(shù)組結(jié)構(gòu)

保存數(shù)組長(zhǎng)度

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

max-heapify是把每一個(gè)不滿足最大堆性質(zhì)的分支節(jié)點(diǎn)進(jìn)行調(diào)整的一個(gè)操作。

如上圖：

調(diào)整分支節(jié)點(diǎn)2（分支節(jié)點(diǎn)2不滿足最大堆的性質(zhì)）

默認(rèn)該分支節(jié)點(diǎn)為最大值

將2與左右分支比較，從2，12，5中找出最大值，然后和2交換位置

根據(jù)上面所將的二叉堆性質(zhì)，分別得到分支節(jié)點(diǎn)2的左節(jié)點(diǎn)和右節(jié)點(diǎn)

比較三個(gè)節(jié)點(diǎn)，得到最大值的下標(biāo)max

如果該節(jié)點(diǎn)本身就是最大值，則停止操作

將max節(jié)點(diǎn)與父節(jié)點(diǎn)進(jì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);
    }

我們可以看到，剛初始化的堆由數(shù)組表示，這個(gè)時(shí)候它可能并不滿足一個(gè)最大堆或最小堆的性質(zhì)，這個(gè)時(shí)候我們可能需要去將整個(gè)堆構(gòu)建成我們想要的。
上面我們做了max-heapify操作，而max-heapify只是將某一個(gè)分支節(jié)點(diǎn)進(jìn)行調(diào)整，而要將整個(gè)堆構(gòu)建成最大堆，則需要將所有的分支節(jié)點(diǎn)都進(jìn)行一次max-heapify操作，如下圖，我們需要依次對(duì)12，3，2，15這4個(gè)分支節(jié)點(diǎn)進(jìn)行max-hepify操作

具體步驟：

找到所有分支節(jié)點(diǎn)：上面堆的性質(zhì)提到過(guò)葉子節(jié)點(diǎn)的序號(hào)>=Math.floor(n/2)，因此小于Math.floor(n/2)序號(hào)的都是我們需要調(diào)整的節(jié)點(diǎn)。

例如途中所示數(shù)組為[15,2,3,12,5,2,8,4,7] => Math.floor(9/2)=4 => index小于4的分別是15，2，3，12(需要調(diào)整的節(jié)點(diǎn))，而5，2，8，4，7為葉子節(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è)元素從堆中拿出，相當(dāng)于堆的size-1

然后在堆根節(jié)點(diǎn)進(jìn)行一次max-heapify操作

重復(fù)以上三個(gè)步驟，知道size=0 (這個(gè)邊界條件我們?cè)趍ax-heapify函數(shù)里已經(jīng)做了)

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

這個(gè)的插入和刪除就相對(duì)比較簡(jiǎn)單了，就是對(duì)一個(gè)數(shù)組進(jìn)行插入和刪除的操作

往末尾插入

堆長(zhǎng)度+1

判斷插入后是否還是一個(gè)最大堆

不是則進(jìn)行重構(gòu)堆

  insert(key) {
    this.data[this.size] = key;
    this.size++
    if (this.isHeap()) {
      return;
    }
    this.rebuildHeap();
  }

刪除數(shù)組中的某個(gè)元素

堆長(zhǎng)度-1

判斷是否是一個(gè)堆

不是則重構(gòu)堆

  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;
  }

  /**
   * 重構(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();
  }

  /**
   * 堆的其他地方都滿足性質(zhì)
   * 唯獨(dú)跟節(jié)點(diǎn)，重構(gòu)堆性質(zhì)
   * @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;

堆講到這里就結(jié)束了，堆在二叉樹(shù)里相對(duì)會(huì)比較簡(jiǎn)單，常常被用來(lái)做排序和優(yōu)先級(jí)隊(duì)列等。堆中比較核心的還是max-heapify這個(gè)操作，以及堆的三個(gè)性質(zhì)。

下一篇應(yīng)該會(huì)介紹二叉搜索樹(shù)。歡迎大家指出文章的錯(cuò)誤，如果有什么寫(xiě)作建議也可以提出。我會(huì)持續(xù)的去寫(xiě)關(guān)于前端的一些技術(shù)文章，如果大家喜歡的話可以關(guān)注一和點(diǎn)個(gè)贊，你的贊是我寫(xiě)作的動(dòng)力。
順便再提一下，我在等第一個(gè)粉絲哈哈

以下個(gè)人公眾號(hào)，歡迎大家關(guān)注，用戶量達(dá)到一定的量，我會(huì)推出一些前端教學(xué)視頻