PriorityQueue [优先队列]

# 什么是优先级队列？

优先级队列是一种抽象的数据类型，其行为类似于普通队列，只是每个元素都有一定的优先级，也就是说，在优先级队列中，具有最高优先级的元素会排在第一位。优先级队列中的元素的优先级将决定元素从优先级队列中被移除的顺序。

优先级队列只支持可比较的元素，这意味着元素是按升序或降序排列的。

例如，假设我们有一些像 1、3、4、8、14、22 这样的数值被插入优先级队列中，对这些数值的排序是从最小到最大。因此，1 号将有最高的优先权，而 22 号将有最低的优先权。

# 优先级队列的特点

优先级队列是队列的扩展，包含以下特点：

优先级队列中的每个元素都有一些与之相关的优先级。
一个具有较高优先级的元素将在删除较低优先级的元素之前被删除。
如果一个优先级队列中的两个元素具有相同的优先级，它们将使用先进先出的原则进行排列。

让我们通过一个例子来理解优先级队列：我们有一个优先级队列，其中包含以下数值：1, 3, 4, 8, 14, 22，所有的值都按升序排列。现在，我们将观察一下执行以下操作后的优先级队列的情况。

poll ()。这个函数将从优先级队列中移除最高优先级的元素。在上面的优先级队列中，'1' 元素的优先级最高，所以它将被从优先级队列中删除。
add (2)。这个函数将在优先级队列中插入 '2' 元素。由于 2 是所有数字中最小的元素，所以它将获得最高的优先级。
poll ()。它将从优先级队列中删除 '2' 元素，因为它拥有最高的优先级队列。
add (5)。它将在 4 后面插入 5 元素，因为 5 比 4 大，比 8 小，所以它将获得优先级队列中的第三高优先级。

# 操作

优先队列至少需要支持下述操作：

插入带优先级的元素（insert_with_priority）
取出具有最高优先级的元素（pull_highest_priority_element）
查看最高优先级的元素（peek）：O (1) 时间复杂度

其它可选的操作：

检查优先级高的一批元素
清空优先队列
批量插入一批元素
合并多个优先队列
调整一个元素的优先级

# 实现

初级实现：

有许多简单低效的实现。如用一个有序的数组；或使用无序数组，在每次取出时搜索全集合，这种方法插入的效率为 $O(1)$ ，但取出时效率为 $O(n)$ 。

典型实现：

出于性能考虑，优先队列用堆来实现，具有 $O(log n)$ 时间复杂度的插入元素性能， $O(n)$ 的初始化构造的时间复杂度。如果使用自平衡二叉查找树，插入与删除的时间复杂度为 $O(log n)$ ，构造二叉树的时间复杂度为 $O(n log n)$ 。

从计算复杂度的角度，优先级队列等价于排序算法。

有一些特殊的堆为优先队列的实现提供了额外的性能：二叉堆的插入与提取操作的时间复杂度为 $O(log n)$ ，并可以常量时间复杂度的 peek 操作。二项堆提供了几种额外操作。斐波那契堆的插入、提取、修改元素优先级等操作具有分摊常量时间复杂度，但删除操作的时间复杂度为 $O(log n)$ 。Brodal queue 具有最糟糕情况下的常量复杂度但算法相当复杂因而不具有实用性。

对于整型、浮点型等具有有限值域的元素的数据类型，优先队列有更快的实现。

# JavaScript

const { Heap } = require('@datastructures-js/heap');

class PriorityQueue {
  /**
   * Creates a priority queue
   * @params {function} compare
   */
  constructor(compare, _values) {
    if (typeof compare !== 'function') {
      throw new Error('PriorityQueue constructor expects a compare function');
    }
    this._heap = new Heap(compare, _values);
    if (_values) {
      this._heap.fix();
    }
  }

  /**
   * Returns an element with highest priority in the queue
   * @public
   * @returns {number|string|object}
   */
  front() {
    return this._heap.root();
  }

  /**
   * Returns an element with lowest priority in the queue
   * @public
   * @returns {number|string|object}
   */
  back() {
    return this._heap.leaf();
  }

  /**
   * Adds a value to the queue
   * @public
   * @param {number|string|object} value
   * @returns {PriorityQueue}
   */
  enqueue(value) {
    return this._heap.insert(value);
  }

  /**
   * Removes and returns an element with highest priority in the queue
   * @public
   * @returns {number|string|object}
   */
  dequeue() {
    return this._heap.extractRoot();
  }

  /**
   * Returns the number of elements in the queue
   * @public
   * @returns {number}
   */
  size() {
    return this._heap.size();
  }

  /**
   * Checks if the queue is empty
   * @public
   * @returns {boolean}
   */
  isEmpty() {
    return this._heap.isEmpty();
  }

  /**
   * Clears the queue
   * @public
   */
  clear() {
    this._heap.clear();
  }

  /**
   * Returns a sorted list of elements from highest to lowest priority
   * @public
   * @returns {array}
   */
  toArray() {
    return this._heap.clone().sort().reverse();
  }

  /**
   * Creates a priority queue from an existing array
   * @public
   * @static
   * @returns {PriorityQueue}
   */
  static fromArray(values, compare) {
    return new PriorityQueue(compare, values);
  }
}

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

参考：

编辑

上次更新: 2022/10/11, 17:42:20

← Queue [队列] MinPriorityQueue [最小优先队列]→