什么是堆？

原文链接：https://note.noxussj.top/?source=helloworld

什么是堆？

堆是一种特殊的完全二叉树。完全二叉树的含义就是每层节点都完全填满，除了最后一层外只允许最右边缺少若干个节点。在 JavaScript 中通常用数组表示堆（按照广度优先遍历顺序）。

最大堆

最小堆

特性

• 所有的节点都大于等于它的子节点（最大堆）
• 或者所有的节点都小于等于它的子节点（最小堆）
• 左侧子节点的位置是 2 _ index + 1
• 右侧子节点的位置是 2 _ index + 2 （也就是在左子节点的基础上 + 1）
• 父节点的位置是 (index - 1) / 2

优点

• 高效、快速的找出堆的最大值和最小值，时间复杂度是 O (1)
• 找出第 K 个最大、最小元素

常用操作

插入

• 将值插入堆的底部，即数据的尾部
• 然后上移，将这个值和它父节点进行交换，直到父节点小于等于这个插入的值
• 大小为 k 的堆中插入元素的时间复杂度为 O (logK)

删除堆顶

• 用数组尾部元素替换堆顶（直接删除堆顶会破坏结构）
• 然后下移，将新堆顶和它的子节点进行交换，直到子节点大于等于这个新堆顶
• 大小为 k 的堆中删除堆顶的时间复杂度为 O (logK)

获取堆顶

• 返回数组的第 0 项

获取堆大小

• 返回数组的长度

基础案例

通过 Class 实现最小堆

1class MinHeap {
2    constructor() {
3        this.heap = []
4    }
5
6    top() {
7        return this.heap[0]
8    }
9
10    size() {
11        return this.heap.length
12    }
13
14    getChildLeftIndex(i) {
15        return i * 2 + 1
16    }
17
18    getChildRightIndex(i) {
19        return i * 2 + 2
20    }
21
22    getParentIndex(i) {
23        return (i - 1) >> 1
24    }
25
26    swap(index1, index2) {
27        const temp = this.heap[index1]
28        this.heap[index1] = this.heap[index2]
29        this.heap[index2] = temp
30    }
31
32    shiftUp(index) {
33        if (index === 0) return
34
35        const parentIndex = this.getParentIndex(index)
36        if (this.heap[parentIndex] > this.heap[index]) {
37            this.swap(parentIndex, index)
38            this.shiftUp(parentIndex)
39        }
40    }
41
42    shiftDown(index) {
43        const leftChildIndex = this.getChildLeftIndex(index)
44        const rightChildIndex = this.getChildRightIndex(index)
45
46        if (this.heap[leftChildIndex] < this.heap[index]) {
47            this.swap(leftChildIndex, index)
48            this.shiftDown(leftChildIndex)
49        }
50
51        if (this.heap[rightChildIndex] < this.heap[index]) {
52            this.swap(rightChildIndex, index)
53            this.shiftDown(rightChildIndex)
54        }
55    }
56
57    insert(value) {
58        this.heap.push(value)
59        this.shiftUp(this.heap.length - 1)
60    }
61
62    pop() {
63        this.heap[0] = this.heap.pop()
64        this.shiftDown(0)
65    }
66}
67
68const h = new MinHeap()
69h.insert(3)
70h.insert(2)
71h.insert(1)
72h.pop()