Published by powerfulyang on Nov 25, 2022

A Heap is a special Tree-based data structure in which the tree is a complete binary tree.

• Heap is array-based data structure.
• It is a complete binary tree.
• Priority Queue is a heap.

Generally, Heaps can be of two types:

1. Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.
2. Min-Heap: In a Min-Heap the key present at the root node must be minimum among the keys present at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.

typescript
Copy Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
class MaxHeap {
  private _heap: number[] = [];

  private swap(index1: number, index2: number) {
    [this._heap[index1], this._heap[index2]] = [this._heap[index2], this._heap[index1]];
  }

  private heapifyUp() {
    // 重新排列
    let lastItem = this._heap.length - 1;
    while (lastItem > 0) {
      // 保持 parentElement >= currentElemnt
      // heap is a complete binary tree
      // parentIndex = Math.floor((index - 1) / 2);
      const parentIndex = Math.floor((index - 1) / 2);
      if (this._heap[lastItem] > this._heap[parentIndex]) {
        this.swap(lastItem, parentIndex);
        lastItem = parentIndex;
      } else {
       lastItem = 0; 
      }
    }
  }

  offer(element: number) {
    this._heap.push(element);
    this.heapifyUp();
  }

  heapifyDown() {
    let index = 0;
    // complete binary tree
    // leftChildIndex = i * 2 + 1
    // rightChildIndex = i * 2 + 2
    while (index < this._heap.length) {
      const leftChildIndex = index * 2 + 1;
      const rightChildIndex = index * 2 + 2;
      let maxChildIndex = leftChildIndex;
      if (rightChildIndex < this._heap.length && this._heap[rightChildIndex] > this._heap[leftChildIndex]) {
        maxChildIndex = rightChildIndex;
      }
      if (this._heap[index] < this._heap[maxChildIndex]) {
        // 比较父节点和子节点的值，如果父节点的值比子节点的值小，则交换
        this.swap(index, maxChildIndex);
        index = maxChildIndex; // 将子节点的索引赋值给循环的索引
      } else {
        break;
      }
    }
  }

  poll() {
    const result = this._heap[0];
    // 将最后一个元素放到第一个元素的位置，然后再弹出最后一个元素
    // 维持 complete binary tree
    this._heap[0] = this._heap.pop();
    // 把堆顶元素移动下去
    this.heapifyDown();
    return result;
  }
}