数据结构-堆
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:
- 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.
- 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
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}