风动之石的博客

堆

数据结构里，需要满足下面两个条件的就是堆：

  • 堆是一个完全二叉树
  • 堆上的任意节点值都必须大于等于（大顶堆）或小于等于（小顶堆）其左右子节点值

堆的实现

堆的类定义

class Heap {
    /**
     * 构造函数
     * @param {array} array 可选，初始数组
     * @param {function} compare 可选，优先级比较函数，默认按数字/字母从小到大排序
     */
    constructor(array, compare) {}

    /**
     * 元素入堆
     */
    push(item) {}

    /**
     * 元素出堆
     */
    pop() {}

    /**
     * 返回堆顶元素，但不删除
     */
    peek() {}


    /**
     * 堆里节点数量
     */
    get size()
}
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

堆的实现源码

使用数组来实现堆时，若数组的索引从0开始的话，则某个索引为i的节点的相关节点索引为：

  • 父节点索引为：Math.floor((i - 1) / 2)
  • 左子节点索引为：2i + 1
  • 右子节点所以为：2i + 2
/**
 * 堆的实现，参考：https://blog.csdn.net/m0_38086372/article/details/108440136
 */
class Heap {
    data = [];

    /**
     * 构造函数
     * @param {array} array 初始数组
     * @param {function} compare, 优先级比较函数，默认按数字/字母从小到大排序
     */
    constructor(array, compare) {
        if (typeof array === 'function') {
            compare = array;
            array = [];
        }

        if (compare) {
            if (typeof compare !== 'function') {
                throw '实例化类 Heap 时，若传入第二个参数，需要是优先级比较函数';
            } else {
                this.compare = compare;
            }
        }

        if (array) {
            if (!Array.isArray(array)) {
                throw '实例化类 Heap 时，第一个参数需要是数组';
            } else {
                array.forEach(ele => {
                    this.push(ele);
                });
            }
        }
    }

    /**
     * 元素入堆，比较该元素与其父节点的优先级，并作出调整
     * （父节点的优先级比左右子节点的优先级要高，所以只需要比较新增节点与其父节点的优先级并做调整）
     *
     * @param {any} ele 新加入的节点
     */
    push(ele) {
        this.data.push(ele);
        this._adjustUp(this.size - 1);
    }

    /**
     * 元素出堆，返回堆里优先级最高的节点，并将其从堆里删除
     *
     * 1. 获取堆顶节点（数组索引为 0）并保存
     * 2. 删除数组最后一个节点（数组索引为 data.length - 1），并将该节点覆盖栈顶节点（数组索引为 0）
     * 3. 调整栈顶节点的优先级
     *     - 只有左子节点：只和该节点比较判断是否交换
     *     - 左右子节点都有：选择左右节点之间优先级较高的进行比较
     * 4. 返回第 1 步保存的节点
     */
    pop() {
        if (this.size === 0) {
            return null;
        }

        // 堆栈节点与最后一个节点互换
        this._swap(0, this.size - 1);
        const result = this.data.pop();


        this._adjustDown(0);

        return result;
    }

    /**
     * 返回堆顶元素，但不删除
     */
    peek() {
        return this.data[0];
    }

    /**
     * 堆中节点数量
     */
    get size() {
        return this.data.length;
    }

    /**
     * 优先级比较函数，返回 true 表示第一个参数优先级更高
     */
    compare(a, b) {
        return  a < b;
    }

    /**
     * 向上调整优先级
     */
    _adjustUp(index) {
        let parentIndex = this._getParentIndex(index);
        while(index > 0 && this.compare(this.data[index], this.data[parentIndex])) {
            this._swap(index, parentIndex);
            index = parentIndex;
            parentIndex = this._getParentIndex(index);
        }
    }

    /**
     * 向下调整优先级
     */
    _adjustDown(index) {
        let len = this.size;

        while(this._getLeftChildIndex(index) < len) {
            let childIndex = this._getLeftChildIndex(index);
            let rightChildIndex = this._getRightChildIndex(index);

            // 若右子节点存在且优先级比左子节点更高，则选择右子节点进行比较
            if (rightChildIndex < len && this.compare(this.data[rightChildIndex], this.data[childIndex])) {
                childIndex = rightChildIndex;
            }

            // 若节点比其子节点优先级更高，则无需再调整了
            if (this.compare(this.data[index], this.data[childIndex])) {
                return;
            }

            this._swap(childIndex, index);
            index = childIndex;
        }
    }

    /**
     * 获取左子节点索引
     */
    _getLeftChildIndex(index) {
        return 2 * index + 1;
    }
    /**
     * 获取右子节点索引
     */
    _getRightChildIndex(index) {
        return 2 * index + 2;
    }
    /**
     * 获取父节点索引
     */
    _getParentIndex(index) {
        return Math.floor((index - 1)/2);
    }

    /**
     * 交互位置
     * @param {any} n
     * @param {any} m
     */
    _swap(n, m) {
        const temp = this.data[n];
        this.data[n] = this.data[m];
        this.data[m] = temp;
    }
}
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160

复杂度分析

时间复杂度

往堆里插入n个元素，时间复杂度: O(nlogn)。

  • 每次插入一个元素调整堆: O(logn)
  • 需要插入n次

每次删除一个元素，时间复杂度: O(logn)

空间复杂度

O(n)

大顶堆和小顶堆

如果堆上的任意节点都大于等于子节点值，则称为大顶堆。如果堆上的任意节点都小于等于子节点值，则称为小顶堆。

也就是说，在大顶堆中，根节点是堆中最大的元素；在小顶堆中，根节点是堆中最小的元素。

大顶堆是指堆顶的优先级最高，小顶堆是指堆顶的优先级最低，可通过实例化Heap时传入不同的compare函数来分别实现大顶堆和小顶堆。

// 大顶堆
new Heap((a, b) => b > a);

// 小顶堆（默认）
new Heap((a, b) => a > b);
new Heap();
1
2
3
4
5
6

应用

获取无序数组里第 K 大的数

function TopK(array, maxIndex) {
    const heap = new Heap();
    array.forEach(item => {
        heap.push(item);
        if (heap.size > maxIndex) {
            heap.pop();
        }
    });
    return heap.pop();
}
1
2
3
4
5
6
7
8
9
10
  • 时间复杂度：O(nlogk)，其中，每次调整堆的时间复杂度为O(logk)
  • 空间复杂度：O(k)