数据结构-堆

Published by powerfulyang on Nov 25, 2022

What is Heap?

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.

Types of 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.

Implementation

typescript
1class MaxHeap {
2  private _heap: number[] = [];
3
4  private swap(index1: number, index2: number) {
5    [this._heap[index1], this._heap[index2]] = [this._heap[index2], this._heap[index1]];
6  }
7
8  private heapifyUp() {
9    // 重新排列
10    let lastItem = this._heap.length - 1;
11    while (lastItem > 0) {
12      // 保持 parentElement >= currentElemnt
13      // heap is a complete binary tree
14      // parentIndex = Math.floor((index - 1) / 2);
15      const parentIndex = Math.floor((index - 1) / 2);
16      if (this._heap[lastItem] > this._heap[parentIndex]) {
17        this.swap(lastItem, parentIndex);
18        lastItem = parentIndex;
19      } else {
20       lastItem = 0; 
21      }
22    }
23  }
24
25  offer(element: number) {
26    this._heap.push(element);
27    this.heapifyUp();
28  }
29
30  heapifyDown() {
31    let index = 0;
32    // complete binary tree
33    // leftChildIndex = i * 2 + 1
34    // rightChildIndex = i * 2 + 2
35    while (index < this._heap.length) {
36      const leftChildIndex = index * 2 + 1;
37      const rightChildIndex = index * 2 + 2;
38      let maxChildIndex = leftChildIndex;
39      if (rightChildIndex < this._heap.length && this._heap[rightChildIndex] > this._heap[leftChildIndex]) {
40        maxChildIndex = rightChildIndex;
41      }
42      if (this._heap[index] < this._heap[maxChildIndex]) {
43        // 比较父节点和子节点的值，如果父节点的值比子节点的值小，则交换
44        this.swap(index, maxChildIndex);
45        index = maxChildIndex; // 将子节点的索引赋值给循环的索引
46      } else {
47        break;
48      }
49    }
50  }
51
52  poll() {
53    const result = this._heap[0];
54    // 将最后一个元素放到第一个元素的位置，然后再弹出最后一个元素
55    // 维持 complete binary tree
56    this._heap[0] = this._heap.pop();
57    // 把堆顶元素移动下去
58    this.heapifyDown();
59    return result;
60  }
61}