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