数据结构（九）堆

数据结构（九）堆

1. 定义

完全二叉树

一种特殊的完全二叉树

所有节点都大于等于(最大堆)或小于等于（最小堆）它的子节点

  • 在js中通常使用数组表示堆

  • 左侧子节点的位置是 2 * index + 1

  • 左侧子节点的位置是 2 * index + 2

  • 父节点位置 (index - 1) / 2

堆的应用：

  • 堆能高效、快速地找出最大值和最小值，时间复杂度为：O(1)
  • 找出第k个最大（小）元素
    • 构建一个最小堆，并将元素依次插入堆中
    • 当堆的容量超过k，就删除堆顶
    • 插入结束后，堆顶就是第k个最大元素

2. 具体操作

最小堆类

构建

1
2
3
4
5
class MinHeap {
    constructor() {
        this.heap = [];
    }
}

方法

  • 插入

    将值插入堆的底部，即数组的尾部

    然后上移：将这个值和它的父节点进行交换，直到父节点等于这个插入的值

    大小为k的堆中插入元素的时间复杂度为O(logk)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    getParentIndex(i) {
        if (index === 0) return undefined;
        return Math.floor((i - 1) / 2);
        // return (i - 1) >> 1;
    }
    swap(i1, i2) {
        const temp = this.heap[i1];
        this.heap[i1] = this.heap[i2];
        this.heap[i2] = temp
        // [this.heap[i1], this.heap[i2]] = [this.heap[i2], this.heap[i1]];
    }
    shiftUp(index) {
        if(index===0) return;
       const parentIndex = this.getParentIndex(index);
        if(this.heap[parentIndex] > this.heap[index]) {
            this.swap(parentIndex, index);
            this.shiftUp(parentIndex);
        }
    }
    insert(value) {
        this.heap.push(value)
        this.shiftUp(this.heap.length - 1);
    }

  • 删除堆顶

    用数组尾部元素替换堆顶（直接删除堆顶会破坏堆的结构）

    然后下移：将新堆顶和它的子节点进行交换，直到子节点大于等于这个新堆顶

    大小为k的堆中删除堆顶的时间复杂度为O(logk)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    getLeftIndex(i) {
        return i * 2 + 1;
    }
    getRightIndex(i) {
        return i * 2 + 2;
    }
    shiftDown(index) {
        const leftIndex = this.getLeftIndex(index);
        const rightIndex = this.getRightIndex(index);
        if(this.heap[leftIndex] < this.heap[index]) {
            this.swap(leftIndex, index);
            this.shiftDown(leftIndex);
        }
        if(this.heap[rightIndex] < this.heap[index]) {
            this.swap(rightIndex, index);
            this.shiftDown(rightIndex);
        }
    }
    pop() {
        this.heap[0] = this.heap.pop()
        this.shiftDown(0)
    }

  • 获取堆顶和堆的大小

    获取堆顶：返回数组的头部

    获取堆的大小：返回数组的长度

    1
    2
    3
    4
    5
    6
    peek() {
        return this.heap[0]
    }
    size() {
        return this.heap.length
    }

    ​

3. 使用

找出第k个最大元素

1
2
3
4
5
6
7
8
const h = new MinHeap();
    nums.forEach(n => {
        h.insert(n);
        if (h.size() > k) {
            h.pop()
        }
    })
    return h.peek()

4. LeetCode题

215. 数组中的第K个最大元素

解题思路：

  • 看到”第K个最大元素“
  • 考虑选择使用最小堆

解题步骤：

  • 构建一个最小堆，并依次把数组的值插入堆中
  • 当堆的容量超过K，就删除堆顶
  • 插入结束后，堆顶就是第K个最大元素
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
class MinHeap {
    constructor() {
        this.heap = [];
    }
    // 交换节点位置
    swap(i1, i2) {
        const temp = this.heap[i1];
        this.heap[i1] = this.heap[i2];
        this.heap[i2] = temp
    }
    // 获得父节点
    getParentIndex(i) {
        return (i - 1) >> 1;
    }
    // 获得左节点
    getleftIndex(i) {
        return i * 2 + 1;
    }
    // 获得右节点
    getrightIndex(i) {
        return i * 2 + 2;
    }
    // 上移
    shiftUp(index) {
        if (index === 0) return;
        const parentIndex = this.getParentIndex(index);
        if (this.heap[parentIndex] > this.heap[index]) {
            this.swap(parentIndex, index);
            this.shiftUp(parentIndex);
        }
    }
    // 下移
    shiftDown(index) {
        const leftIndex = this.getleftIndex(index);
        const rightIndex = this.getrightIndex(index);
        if (this.heap[leftIndex] < this.heap[index]) {
            this.swap(leftIndex, index);
            this.shiftDown(leftIndex);
        }
        if (this.heap[rightIndex] < this.heap[index]) {
            this.swap(rightIndex, index);
            this.shiftDown(rightIndex);
        }
    }
    // 插入
    insert(value) {
        this.heap.push(value);
        this.shiftUp(this.heap.length - 1);
    }
    // 删除堆顶
    pop() {
        this.heap[0] = this.heap.pop();
        this.shiftDown(0);
    }
    // 获取堆顶
    peek() {
        return this.heap[0];
    }
    // 获取堆的大小
    size() {
        return this.heap.length;
    }
}

const findKthLargest = (nums, k) => {
    const h = new MinHeap();
    nums.forEach(n => {
        h.insert(n);
        if (h.size() > k) {
            h.pop()
        }
    })
    return h.peek()
};

347. 前 K 个高频元素

1
2
3
4
5
6
7
8
var topKFrequent = function (nums, k) {
    const map = new Map();
    nums.forEach(n => {
        map.set(n, map.has(n) ? map.get(n) + 1 : 1);
    })
    const list = Array.from(map).sort((a, b) => b[1] - a[1]);
    return list.slice(0, k).map(n => n[0])
};

使用堆进行优化：

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
class MinHeap {
    constructor() {
        this.heap = [];
    }
    // 交换节点位置
    swap(i1, i2) {
        const temp = this.heap[i1];
        this.heap[i1] = this.heap[i2];
        this.heap[i2] = temp
    }
    // 获得父节点
    getParentIndex(i) {
        return (i - 1) >> 1;
    }
    // 获得左节点
    getleftIndex(i) {
        return i * 2 + 1;
    }
    // 获得右节点
    getrightIndex(i) {
        return i * 2 + 2;
    }
    // 上移
    shiftUp(index) {
        if (index === 0) return;
        const parentIndex = this.getParentIndex(index);
        if (this.heap[parentIndex] && this.heap[parentIndex].value > this.heap[index].value) {
            this.swap(parentIndex, index);
            this.shiftUp(parentIndex);
        }
    }
    // 下移
    shiftDown(index) {
        const leftIndex = this.getleftIndex(index);
        const rightIndex = this.getrightIndex(index);
        if (this.heap[leftIndex] && this.heap[leftIndex].value < this.heap[index].value) {
            this.swap(leftIndex, index);
            this.shiftDown(leftIndex);
        }
        if (this.heap[rightIndex] && this.heap[rightIndex].value < this.heap[index].value) {
            this.swap(rightIndex, index);
            this.shiftDown(rightIndex);
        }
    }
    // 插入
    insert(value) {
        this.heap.push(value);
        this.shiftUp(this.heap.length - 1);
    }
    // 删除堆顶
    pop() {
        this.heap[0] = this.heap.pop();
        this.shiftDown(0);
    }
    // 获取堆顶
    peek() {
        return this.heap[0];
    }
    // 获取堆的大小
    size() {
        return this.heap.length;
    }
}
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function (nums, k) {
    const map = new Map();
    nums.forEach(n => {
        map.set(n, map.has(n) ? map.get(n) + 1 : 1);
    })
    const h = new MinHeap();
    map.forEach((value, key) => {
        h.insert({ value, key });
        if (h.size() > k) {
            h.pop()
        }
    })
    return h.heap.map(a => a.key)
};

23. 合并K个升序链表

解题思路：

  • 新链表的下一个节点一定是k个链表头中的最小节点
  • 考虑选择使用最小堆

解题步骤：

  • 构建一个最小堆，并依次把链表头插入堆中
  • 弹出堆顶接到输出链表，并将堆顶所在链表的新链表头插入堆中
  • 等堆元素全部弹出，合并工作就完成了
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
class MinHeap {
    constructor() {
        this.heap = [];
    }
    // 交换节点位置
    swap(i1, i2) {
        const temp = this.heap[i1];
        this.heap[i1] = this.heap[i2];
        this.heap[i2] = temp
    }
    // 获得父节点
    getParentIndex(i) {
        return (i - 1) >> 1;
    }
    // 获得左节点
    getleftIndex(i) {
        return i * 2 + 1;
    }
    // 获得右节点
    getrightIndex(i) {
        return i * 2 + 2;
    }
    // 上移
    shiftUp(index) {
        if (index === 0) return;
        const parentIndex = this.getParentIndex(index);
        if (this.heap[parentIndex] && this.heap[parentIndex].val > this.heap[index].val) {
            this.swap(parentIndex, index);
            this.shiftUp(parentIndex);
        }
    }
    // 下移
    shiftDown(index) {
        const leftIndex = this.getleftIndex(index);
        const rightIndex = this.getrightIndex(index);
        if (this.heap[leftIndex] && this.heap[leftIndex].val < this.heap[index].val) {
            this.swap(leftIndex, index);
            this.shiftDown(leftIndex);
        }
        if (this.heap[rightIndex] && this.heap[rightIndex].val < this.heap[index].val) {
            this.swap(rightIndex, index);
            this.shiftDown(rightIndex);
        }
    }
    // 插入
    insert(value) {
        this.heap.push(value);
        this.shiftUp(this.heap.length - 1);
    }
    // 删除堆顶
    pop() {
        if (this.size() === 1) return this.heap.shift();
        const top = this.heap[0]
        this.heap[0] = this.heap.pop();
        this.shiftDown(0);
        return top;
    }
    // 获取堆顶
    peek() {
        return this.heap[0];
    }
    // 获取堆的大小
    size() {
        return this.heap.length;
    }
}
/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode[]} lists
 * @return {ListNode}
 */
var mergeKLists = function (lists) {
    const res = new ListNode(0);
    let p = res;
    const h = new MinHeap()
    lists.forEach(list => {
        if (list) h.insert(list)
    })
    while (h.size()) {
        const n = h.pop();
        p.next = n;
        p = p.next;
        if (n.next) h.insert(n.next);
    }
    return res.next;
};