---
tags: DSA in JavaScript
---
# Ch.24 Binary Heaps

接下來就到了另一個樹狀結構 --- Heap (堆疊)
堆疊有滿多種使用方式的，較為基本的應用是 Max/Min Binary Heaps

以 Max Binary Heaps 為例，這個結構有以下特性：

- 最大的節點永遠會在樹的根部
- 父節點永遠會大於子節點
- 不能保證同一層子節點的大小
- 節點是由左而右進行新增的
- 每一層都填滿節點時才會新增至下一層

與常見的樹狀結構不同，這類堆疊是使用陣列來儲存節點，然後用以下方式來儲存父節點或子節點的位置。

假設一節點為陣列的第 n 元素

- 該節點的父節點為陣列第 $\frac {n-1} {2}$ (取整數) 元素
- 左邊子節點為陣列第 $2n + 1$ 元素
- 右邊子節點為陣列第 $2n + 2$ 元素


基本的程式碼實作起來也很簡單，裡面只要一個陣列就行了。

class MaxBinaryHeap {
  constructor () {
    this.values = []
  }
}

## insert(value)

第一個要介紹的方法是新增節點，與其他結構不同，在陣列最尾端新增節點後，若新節點大於父節點，必須對調兩者位置，直到新節點不再大於父節點，因此會在新增一個 `bubbleUp` 方法來實作新節點「上浮」的過程。

insert (value) {
  const { values } = this
  // 1. 將新節點新增到最尾端
  values.push(value)
  // 2. 開始 bubbleUp
  // 2-1. 找出新節點與它父節點的位置
  let idx = values.length - 1
  let parentIndex = (idx - 1) >> 1
  // 2-2. 直到新節點不大於父節點，或是新節點已經上升到根部
  while (values[parentIndex] < values[idx] && idx > 0) {
    // 2-3. 互換新節點與父節點的位置
    const temp = values[parentIndex]
    values[parentIndex] = values[idx]
    values[idx] = temp
    // 2-4. 更新新節點位置，還有父節點的相對位置
    idx = parentIndex
    parentIndex = (idx - 1) >> 1
  }
}

## extractMax

第二個方法就是移除根節點，並且再移除根節點後，將最後一個節點補上來，再將該節點「下沉」，直到沒有比該節點大的子節點為止，最後回傳根節點，「下沉」詳細步驟會以 `sinkDown` 函式實作。

extractMax () {
  const max = this.values[0]
  const end = this.values.pop()
  // 若有兩個以上的節點才需要 sinkDown
  if (this.values.length) {
    this.values[0] = end
    this.sinkDown()
  }
  return max
}

sinkDown () {
  let idx = 0
  const { length } = this.values
  // 此處的 element 是被換位的節點
  const element = this.values[0]
  while (true) {
    // 1. 宣告左右子節點與其位置
    //    swap 是最後 element 要交換的位置
    const leftChildIdx = 2 * idx + 1
    const rightChildIdx = leftChildIdx + 1
    let leftChild
    let rightChild
    let swap = null
    // 2. 先以左節點開始
    // 2-1. 檢查節點位置有沒有超出陣列範圍
    if (leftChildIdx < length) {
      leftChild = this.values[leftChildIdx]
      // 2-2. 若子節點大於 element，則將子節點的位置作為 element 的更換點
      if (leftChild > element) {
        swap = leftChildIdx
      }
    }
    // 3. 再以右子節點開始，檢查是否超出範圍
    if (rightChildIdx < length) {
      rightChild = this.values[rightChildIdx]
      // 3-1. 無更換點(左子節點小於 element) + 右子節點大於 element，
      // 或是 右子節點大於其他兩個節點，將右子節點的位置做為更換點
      if (
        (swap === null && rightChild > element) ||
        (swap !== null && rightChild > leftChild)
      ) {
        swap = rightChildIdx
      }
    }
    // 4. 若是都沒有更換，代表 element 大於其他兩個子節點，跳脫迴圈
    if (swap === null) break
    // 5. 將 element 與 swap 指定的位置對調
    this.values[idx] = this.values[swap]
    this.values[swap] = element
    // 6. 更新 element 的位置，進入下個迴圈
    idx = swap
  }
}

<style>
img {
height: 500px;
}
</style>