frenchleave

JavaScript实现最小堆和最大堆

2022/2/23 JavaScriptAlgorithm

# 概念

最大堆（大根堆、大顶堆） (opens new window)和最小堆（小根堆、小顶堆） (opens new window)：

堆是一种经过排序的完全二叉树，其中任一非终端节点的数据值均不大于（或不小于）其左子节点和右子节点的值。

最大堆和最小堆是二叉堆的两种形式。

最大堆根结点的键值是所有堆结点键值中最大者。

最小堆根结点的键值是所有堆结点键值中最小者。

TIPS

JavaScript中堆和优先队列更完整的实现：heap (opens new window)，priority-queue (opens new window)

# 最小堆

// 插入和删除的时间复杂度都是 O(logn)
class MinHeap {
  constructor(data) {
    if (Array.isArray(data)) {
      this.heap = data.slice();
      if (this.heap.length > 1) {
        this.heapify();
      }
    } else {
      this.heap = [];
    }
  }

  insert(value) {
    this.heap.push(value);
    this.shiftUp(this.heap.length - 1);
  }

  pop() {
    if (this.size() === 0) return null;
    if (this.size() === 1) {
      return this.heap.pop();
    }
    const data = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.shiftDown(0);
    return data;
  }

  peek() {
    return this.heap[0];
  }

  size() {
    return this.heap.length;
  }

  getParentIndex(i) {
    return (i - 1) >> 1;
  }

  getLeftIndex(i) {
    return i * 2 + 1;
  }

  getRightIndex(i) {
    return i * 2 + 2;
  }

  swap(i1, i2) {
    const temp = this.heap[i1];
    this.heap[i1] = this.heap[i2];
    this.heap[i2] = temp;
  }

  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);
    let j = leftIndex;
    if (leftIndex < this.size()) {
      // j + 1 表示右孩子节点 找到左右子节点最小的那个
      if (j + 1 < this.size() && this.heap[j + 1] < this.heap[j]) {
        j++;
      }
      // 父节点与最小的子节点交换
      if (this.heap[index] > this.heap[j]) {
        this.swap(j, index);
        // 把最小子节点处的值继续执行下滑操作
        this.shiftDown(j);
      }
    }
  }

  // 将初始数组整理成堆
  heapify() {
    for (let index = this.getParentIndex(this.size() - 1); index >= 0; index--) {
      this.shiftDown(index);
    }
  }
}
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

层序遍历的结果为：[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]（注意：相同元素组成的小根堆不一定都是这样，比如此时1和2的节点交换，仍然是小根堆）

TIPS

最小堆层序遍历的结果序列中，对于序列下标为i（下标从0开始）的元素：

  • 父节点的下标：parent(i) = Math.floor((i - 1) / 2)
  • 左孩子的下标：left(i) = i * 2 + 1
  • 右孩子的下标：right(i) = left(i) + 1 = i * 2 + 2

方法说明

  1. constructor

    接收一个number类型的数组作为初始化的值，否则堆为空。堆中保存的值是二叉树层序遍历的结果，并且这棵二叉树是完全二叉树。

  2. insert

    往堆中插入一个number类型的值。插入的值需要在该堆中做上滑操作（shiftUp）调整所处位置以保证是一个最小堆。

  3. pop

    删除最小堆的根节点，并返回它的值。删除之后的根节点的位置用最后一个子节点来补齐，此时的根节点不一定是最小的，所以需要执行下滑操作（shiftDown）。

  4. peek

    返回最小堆中根节点的值（即最小的值）。

  5. size

    返回最小堆的大小（节点个数）。

  6. getParentIndex

    返回当前节点的父节点在最小堆层序遍历序列中的索引。

  7. getLeftIndex

    返回当前节点的左孩子节点在最小堆层序遍历序列中的索引。

  8. getRightIndex

    返回当前节点的右孩子节点在最小堆层序遍历序列中的索引。

  9. swap

    交换两个索引处的值。

  10. shiftUp

    节点的上滑操作

    • 如果当前节点的索引为0（即根节点），则不做任何处理
    • 对比当前节点与父节点的大小，当前节点的值比父节点的值小，则交换两个节点的值，继续递归往上做上滑操作

  11. shiftDown

    节点的下滑操作

    • 找到两个子节点中值最小的，如果子节点的值更小，那就应该与子节点交换，并且继续递归执行下滑操作

  12. heapify

    将初始数组整理成堆

有何用处？

  • 堆排序
  • TOP K 问题，求前k个最大或者最小元素

# 最大堆

class MaxHeap {
  constructor(data) {
    if (Array.isArray(data)) {
      this.heap = data.slice();
      if (this.heap.length > 1) {
        this.heapify();
      }
    } else {
      this.heap = [];
    }
  }

  insert(value) {
    this.heap.push(value);
    this.shiftUp(this.heap.length - 1);
  }

  pop() {
    if (this.size() === 0) return null;
    if (this.size() === 1) {
      return this.heap.pop();
    }
    const data = this.heap[0];
    this.heap[0] = this.heap.pop();
    this.shiftDown(0);
    return data;
  }

  peek() {
    return this.heap[0];
  }

  size() {
    return this.heap.length;
  }

  getParentIndex(i) {
    return (i - 1) >> 1;
  }

  getLeftIndex(i) {
    return i * 2 + 1;
  }

  getRightIndex(i) {
    return i * 2 + 2;
  }

  swap(i1, i2) {
    const temp = this.heap[i1];
    this.heap[i1] = this.heap[i2];
    this.heap[i2] = temp;
  }

  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);
    let j = leftIndex;
    if (leftIndex < this.size()) {
      if (j + 1 < this.size() && this.heap[j + 1] > this.heap[j]) {
        j++;
      }
      if (this.heap[index] < this.heap[j]) {
        this.swap(j, index);
        this.shiftDown(j);
      }
    }
  }

  heapify() {
    for (let index = this.getParentIndex(this.size() - 1); index >= 0; index--) {
      this.shiftDown(index);
    }
  }
}
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

# 通用优化精简版

class PriorityQueue {
  /**
   * @param {function} compare
   * @param {array} values
   */
  constructor(compare, values) {
    if (typeof compare !== 'function') {
      throw new Error('Heap constructor expects a compare function');
    }
    this.compare = compare;
    this.nodes = Array.isArray(values) ? [...values] : [];
    if (this.size() > 1) {
      this.heapify();
    }
  }

  /**
   * 获取堆中节点数量
   * @returns {number}
   */
  size() {
    return this.nodes.length;
  }

  /**
   * 判断堆是否为空
   * @returns {boolean}
   */
  isEmpty() {
    return this.size() === 0;
  }

  /**
   * 清空堆数据
   */
  clear() {
    this.nodes = [];
  }

  /**
   * 交换两个索引处的值
   * @param {number} i
   * @param {number} j
   */
  swap(i, j) {
    const temp = this.nodes[i];
    this.nodes[i] = this.nodes[j];
    this.nodes[j] = temp;
  }

  /**
   * 初始化数组
   * @returns {Heap}
   */
  heapify() {
    for (let i = 0; i < this.size(); i++) {
      this.shiftUp(i);
    }
    return this;
  }

  /**
   * 节点上浮
   * @param {number} index
   */
  shiftUp(index) {
    let child = index;
    let parent = (child - 1) >> 1;
    // 如果比较函数返回值为truth 则与父节点交换
    while (child > 0 && this.compare(this.nodes[child], this.nodes[parent])) {
      this.swap(parent, child);
      child = parent;
      parent = (child - 1) >> 1;
    }
  }

  /**
   * 节点下沉
   * @param {number} index
   */
  shiftDown(index) {
    let parent = index;
    let child = parent * 2 + 1; // 左孩子节点
    while (child < this.size()) {
      // child + 1 表示的是右孩子节点，如果左右孩子节点比较返回值为truth，说明右孩子更大或者更小
      if (child + 1 < this.size() && this.compare(this.nodes[child + 1], this.nodes[child])) {
        child++;
      }
      // 父节点与左右孩子节点中更大或者更小的进行交换
      if (this.compare(this.nodes[child], this.nodes[parent])) {
        this.swap(parent, child);
        parent = child;
        child = parent * 2 + 1;
      } else {
        break;
      }
    }
  }

  /**
   * 往堆中插入一个值
   * @param {number|string|object} value
   * @returns {Heap}
   */
  insert(value) {
    this.nodes.push(value);
    this.shiftUp(this.size() - 1);
    return this;
  }

  /**
   * 移除并返回堆顶元素
   * @returns {number|string|object}
   */
  pop() {
    if (this.isEmpty()) return null;
    const root = this.nodes[0];
    this.nodes[0] = this.nodes[this.size() - 1];
    this.nodes.pop();
    this.shiftDown(0);
    return root;
  }

  /**
   * 获取堆顶元素
   * @returns {number|string|object}
   */
  peek() {
    if (this.isEmpty()) return null;
    return this.nodes[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
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

TIPS

  1. 比较函数compare(a, b)

    • 大根堆：(a, b) => a > b
    • 小根堆：(a, b) => a < b
    • 如果a与b相比，返回值为truth，a节点应该更往根节点靠
    • 如果a与b相比，返回值为falsy，a节点应该更往叶子节点靠

  2. 上滑（shiftUp）操作

    compare(this.nodes[child], this.nodes[parent])，比较返回值为truth，表示应该交换父子节点，子节点child应该更往根节点靠

  3. 下沉（shiftDown）操作

    • compare(this.nodes[child + 1], this.nodes[child])，如果当前表示的是大根堆，那么返回值为truth说明右节点更大，父节点应该与最大的子节点即当前的右节点交换。如果是小根堆，返回值为truth说明右节点更小，父节点应该和最小的子节点即当前的右节点交换

    • compare(this.nodes[child], this.nodes[parent]，child表示左右子节点中最大或者最小的节点，如果当前是大根堆，并且父节点比最大的子节点都还大，不需要交换，已经满足大根堆要求。如果当前是小根堆，并且父节点比最小的子节点还小，也不需要交换就已经满足小根堆要求

用法

// 数字类型数组
const numberArr = [2, 3, 4, 5, 1, 0, 99, 22, 29, 10];
const numberMinPriority = new PriorityQueue((a, b) => a < b, numberArr);
const numberMaxPriority = new PriorityQueue((a, b) => a > b, numberArr);

// 对象数组
const objectArr = [
  { name: 'AAA', age: 20 },
  { name: 'BBB', age: 56 },
  { name: 'CCC', age: 12 },
  { name: 'DDD', age: 7 },
  { name: 'EEE', age: 66 },
  { name: 'FFF', age: 99 },
];
const objectMinPriority = new PriorityQueue((a, b) => a.age < b.age, objectArr);
const objectMaxPriority = new PriorityQueue((a, b) => a.age > b.age, objectArr);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
最近更新: 2024年09月04日 17:57:58

图论算法之Dijkstra和Floyd