文章

資料結構 - Heap

文章發表於

Heap 資料結構

Heap 是一種特殊的樹狀資料結構，該結構必須符合兩個條件：

  1. 完全二元樹 (Complete Binary Tree)
  2. 節點的值必須大於等於 (maxHeap) 或小於等於 (minHeap) 其子節點的值

舉 minHeap 來說

  1. 第一張圖只有一個節點，兩者皆符合
  2. 第二張圖則是一個完全二元樹，節點也都小於等於其子節點，也符合 minHeap 的條件
  3. 第三張圖儘管節點都小於等於其子節點，但並不是完全二元樹，因此不符合 minHeap 的條件
✅✅❌

API

class Heap {
  constructor() {}
  /** get the top element */
  extractRoot() {}
  /** insert a new element */
  insert() {}
  /** get the size of heap */
  size() {}
  /** peek the top element */
  peek() {}
}

constructor

Heap 的 constructor 一開始需要放入比較函式，在每次 Heapify (往上移動) 的過程中都會透過該比較函式來決定是否要交換節點的位置，比較函式的定義如下：

class Heap {
  constructor(compare) {
    if (typeof compare !== 'function') {
      throw new Error('Heap constructor expects a compare function')
    }
    // 比較函式
    this._compare = compare
    // 用 Array 作為 Heap 的儲存結構
    this._nodes = []
    // 儲存 min heap 最大的節點
    this._leaf = null
  }
}

Insert

首先我們先來看如何插入一個值到 Heap 中，假設我們要插入 3，首先會將 3 插入到 Heap 的最後一個位置，然後再進行 Heapify， 而 Heapify 的過程就是將 3 與其母節點進行比較，如果 3 比母節點小，則將其交換位置，直到 3 比母節點大或是已經到達根節點為止。

pesudo code

class Heap {
  constructor() {}
  insert(value) {
    // 插入到最後一個位置
    this.nodes.push(value)
    // 將該值進行 Heapify
    this.heapifyUp(this.size() - 1)
    // 儲存 min heap 最大的節點
    if (this._compare(value, this.leaf) > 0) {
      this.leaf = value
    }
  }
}

視覺化

實作

實踐 insert 方法，首先我們先來看看如何實作 heapifyUp，heapifyUp 的過程就是將最新插入的節點與其母節點進行比較，如果該節點比母節點小，則將其交換位置，直到最新插入的節點比母節點大或是已經到達根節點為止。

  1. 找出最新插入的節點 (this._nodes[this.size() - 1]) 以及其母節點 (Math.floor((childIndex - 1) / 2))
class Heap {
  heapifyUp(idx) {
    // Step 1
    let childIndex = idx
    let parentIndex = Math.floor((childIndex - 1) / 2)


    // TODO: Step 2
    // ...
  }
}
  1. 比較兩個節點的值
class Heap {
  _compareAt(i, j) {
    return this._compare(this._nodes[i], this._nodes[j])
  }
  _shouldSwap(parentIndex, childIndex) {
    return this._compareAt(parentIndex, childIndex) > 0
  }
  heapifyUp(idx) {
    // Step 1
    let childIndex = idx
    let parentIndex = Math.floor((childIndex - 1) / 2)


    // Step 2
    while (this._shouldSwap(parentIndex, childIndex)) {
      // TODO: Step 3
    }
  }
}
  1. 如果最新插入的節點比母節點小，則交換位置，並且繼續往上比較，直到最新插入的節點比母節點大或是已經到達根節點為止
class Heap {
  heapifyUp(idx) {
    // Step 1
    let childIndex = idx
    let parentIndex = Math.floor((childIndex - 1) / 2)


    // Step 2
    while (this._shouldSwap(parentIndex, childIndex)) {
      // Step 3
      this._swap(parentIndex, childIndex)
      childIndex = parentIndex
      parentIndex = Math.floor((childIndex - 1) / 2)
    }
  }
}

最後則是將 minHeap insert 方法實作出來，首先我們先將新的節點插入到最後一個位置，然後再進行 heapifyUp 的過程，並記錄該 minHeap 最大的節點

class Heap {
  insert(value) {
    this._nodes.push(value)
    this._heapifyUp(this.size() - 1)
    if (this._leaf === null || this._compare(value, this._leaf) > 0) {
      this._leaf = value
    }
  }
}
const http = require('http');

const hostname = '127.0.0.1';
const port = 3000;

const server = http.createServer((req, res) => {
  res.statusCode = 200;
  res.setHeader('Content-Type', 'text/html');
  res.end('Hello world');
});

server.listen(port, hostname, () => {
  console.log(`Server running at http://${hostname}:${port}/`);
});

extractRoot

再來看看我們如何從 minHeap 中取出最小的節點，首先我們會先將根 (root) 節點取出，然後再將最後一個節點放到根節點的位置，接著再進行 heapifyDown 的過程，而 heapifyDown 的過程就是將根節點與其子節點進行比較，如果該節點比子節點大，則將其交換位置，直到該節點比子節點小或是已經到達葉節點為止。

視覺化

實作

實作 extractRoot 我們可以分成兩個步驟：

  1. 將根節點取出，並將最後一個節點放到根節點的位置
class Heap {
  // ...
  extractRoot() {
    if (this.size() === 0) {
      return null
    }


    // Step 1
    const root = this._nodes[0]


    this._nodes[0] = this._nodes[this.size() - 1]
    this._nodes.pop()


    // TODO: Step 2
  }
  // ...
}
  1. 將根節點與其子節點進行比較，如果該節點比子節點大，則將其交換位置，直到該節點比子節點小或是已經到達葉節點為止
class Heap {
  // ...
  _hasLeftChild(parentIndex) {
    let leftChildIndex = parentIndex * 2 + 1
    return leftChildIndex < this.size()
  }
  _hasRightChild(parentIndex) {
    let rightChildIndex = parentIndex * 2 + 2
    return rightChildIndex < this.size()
  }
  _compareChildrenOf(parentIndex) {
    if (!this._hasLeftChild(parentIndex) && !this._hasRightChild(parentIndex)) {
      return null
    }


    const leftChildIndex = parentIndex * 2 + 1
    const rightChildIndex = parentIndex * 2 + 2


    if (!this._hasLeftChild(parentIndex)) {
      return rightChildIndex
    }


    if (!this._hasRightChild(parentIndex)) {
      return leftChildIndex
    }


    return this._compareAt(leftChildIndex, rightChildIndex) > 0 ? rightChildIndex : leftChildIndex
  }
  _heapifyDown(idx) {
    let parentIndex = idx
    let childIndex = this._compareChildrenOf(parentIndex)


    while (this._shouldSwap(parentIndex, childIndex)) {
      this._swap(parentIndex, childIndex)
      parentIndex = childIndex
      childIndex = this._compareChildrenOf(parentIndex)
    }
  }
  extractRoot() {
    if (this.size() === 0) {
      return null
    }


    // Step 1
    const root = this._nodes[0]


    this._nodes[0] = this._nodes[this.size() - 1]
    this._nodes.pop()


    // Step 2
    this._heapifyDown(0)


    if (root === this._leaf) {
      this._leaf = this._nodes[0]
    }


    return root
  }
  // ...
}
const http = require('http');

const hostname = '127.0.0.1';
const port = 3000;

const server = http.createServer((req, res) => {
  res.statusCode = 200;
  res.setHeader('Content-Type', 'text/html');
  res.end('Hello world');
});

server.listen(port, hostname, () => {
  console.log(`Server running at http://${hostname}:${port}/`);
});

總結

最後 Heap 的時間複雜度與空間複雜度如下：

Insert 的操作是在 Array 的最後插入，在進行 heapifyUp 的操作。而 heapifyUp 最壞情況下需要遍歷從末尾到根的路徑，其長度為樹的高度，因此時間複雜度為 O(log n)。

同理 extractRoot 的操作是將根與最後一個元素交換，再進行 heapifyDown 的操作，最壞情況下也需要遍歷從根到葉子的路徑，其長度為樹的高度，因此時間複雜度也為 O(log n)。

而 peekRoot 的操作只是取得根的值，因此時間複雜度為 O(1)。

操作時間複雜度空間複雜度
insertO(log n)O(n)
extractRootO(log n)O(n)
peekRootO(1)O(1)

下一篇，我們將介紹如何使用 Heap 來實作 Priority Queue。

參考資料

  1. CS61B Heap

Leetcode

如果您喜歡這篇文章，請點擊下方按鈕分享給更多人，這將是對筆者創作的最大支持和鼓勵。
Share on Twitter