实现优先队列¶
统计信息：字数 8323 阅读17分钟
所谓优先队列，就是一种特殊的队列, 其底层使用堆的结构，使得每次添加或者删除，让队首元素始终是优先级最高的。关于优先级通过什么字段、按照什么样的比较方式来设定，可以由我们自己来决定。
要实现优先队列，首先来实现一个堆的结构。
关于堆的说明¶
可能你以前没有接触过堆这种数据结构，但是其实是很简单的一种结构，其本质就是一棵二叉树。但是这棵二叉树比较特殊，除了用数组来依次存储各个节点(节点对应的数组下标和层序遍历的序号一致)之外，它需要保证任何一个父节点的优先级大于子节点，这也是它最关键的性质，因为保证了根元素一定是优先级最高的。
举一个例子:
现在这个堆的数组就是: [10, 7, 2, 5, 1]
因此也会产生两个非常关键的操作——siftUp 和 siftDown。
对于siftUp操作，我们试想一下现在有一个正常的堆，满足任何父元素优先级大于子元素，这时候向这个堆的数组末尾又添加了一个元素，那现在可能就不符合堆的结构特点了。那么现在我将新增的节点和其父节点进行比较，如果父节点优先级小于它，则两者交换，不断向上比较直到根节点为止，这样就保证了堆的正确结构。而这样的操作就是siftUp。
siftDown是与其相反方向的操作，从上到下比较，原理相同，也是为了保证堆的正确结构。
实现一个最大堆¶
最大堆，即堆顶元素为优先级最高的元素。
// 以最大堆为例来实现一波
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
class MaxHeap {
constructor(arr = [], compare = null) {
this.data = arr;
this.size = arr.length;
this.compare = compare;
}
getSize() {
return this.size;
}
isEmpty() {
return this.size === 0;
}
// 增加元素
add(value) {
this.data.push(value);
this.size++;
// 增加的时候把添加的元素进行 siftUp
this._siftUp(this.getSize() - 1);
}
// 找到优先级最高的元素
findMax() {
if (this.getSize() === 0)
return;
return this.data[0];
}
// 让优先级最高的元素(即队首元素)出队
extractMax() {
// 1.保存队首元素
let ret = this.findMax();
// 2.让队首和队尾元素交换位置
this._swap(0, this.getSize() - 1);
// 3. 把队尾踢出去，size--
this.data.pop();
this.size--;
// 4. 新的队首 siftDown
this._siftDown(0);
return ret;
}
toString() {
console.log(this.data);
}
_swap(i, j) {
[this.data[i], this.data[j]] = [this.data[j], this.data[i]];
}
_parent(index) {
return Math.floor((index - 1) / 2);
}
_leftChild(index) {
return 2 * index + 1;
}
_rightChild(index) {
return 2 * index + 2;
}
_siftUp(k) {
// 上浮操作，只要子元素优先级比父节点大，父子交换位置，一直向上直到根节点
while (k > 0 && this.compare(this.data[k], this.data[this._parent(k)])) {
this._swap(k, this._parent(k));
k = this._parent(k);
}
}
_siftDown(k) {
// 存在左孩子的时候
while (this._leftChild(k) < this.size) {
let j = this._leftChild(k);
// 存在右孩子而且右孩子比左孩子大
if (this._rightChild(k) < this.size &&
this.compare(this.data[this._rightChild(k)], this.data[j])) {
j++;
}
if (this.compare(this.data[k], this.data[j]))
return;
// 父节点比子节点小，交换位置
this._swap(k, j);
// 继续下沉
k = j;
}
}
}
实现优先队列¶
有了最大堆作铺垫，实现优先队列就易如反掌，废话不多说，直接放上代码。
class PriorityQueue {
// max 为优先队列的容量
constructor(max, compare) {
this.max = max;
this.compare = compare;
this.maxHeap = new MaxHeap([], compare);
}
getSize() {
return this.maxHeap.getSize();
}
isEmpty() {
return this.maxHeap.isEmpty();
}
getFront() {
return this.maxHeap.findMax();
}
enqueue(e) {
// 比当前最高的优先级的还要高，直接不处理
if (this.getSize() === this.max) {
if (this.compare(e, this.getFront())) return;
this.dequeue();
}
return this.maxHeap.add(e);
}
dequeue() {
if (this.getSize() === 0) return null;
return this.maxHeap.extractMax();
}
}
怎么样，是不是非常简单？传说中的优先队列也不过如此。
且慢，可能会有人问: 你怎么保证这个优先队列是正确的呢?
我们不妨来做一下测试:
let pq = new PriorityQueue(3);
pq.enqueue(1);
pq.enqueue(333);
console.log(pq.dequeue());
console.log(pq.dequeue());
pq.enqueue(3);
pq.enqueue(6);
pq.enqueue(62);
console.log(pq.dequeue());
console.log(pq.dequeue());
console.log(pq.dequeue());
结果如下:
333
1
62
6
3
可见，这个优先队列的功能初步满足了我们的预期。后面，我们将通过实际的例子来运用这种数据结构来解决问题。
← 无权图 BFS 遍历
优先队列应用
前 K 个高频元素¶
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
说明:
- 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
- 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
来源: LeetCode第347题
思路¶
首先要做的肯定是统计频率，那之后如何来选取频率前 K 个元素同时又保证时间复杂度小于 O(n log n)呢？
当然，这是一道典型的考察优先队列的题，利用容量为 K 的优先队列每次踢出不符合条件的值，那么最后剩下的即为所求。整个时间复杂度成为 O（n log K），明显是小于 O(n log n) 的。
既然是优先队列，就涉及到如何来定义优先级的问题。
倘若我们以高频率为高优先级，那么队首始终是高频率的元素，因此每次出队是踢出出现频率最高的元素，假设优先队列容量为 K，那照这么做，剩下的是频率最低的 K 个元素，显然不符合题意。
因此，我们需要的是每次出队时踢出频率最低的元素，这样最后剩下来的就是频率最高 K 个元素。
是不是我们为了踢出频率最低的元素，还要重新写一个小顶堆的实现呢？
完全不需要！就像我刚才所说的，合理地定义这个优先级的比较逻辑即可。接下来我们来具体实现一下。
代码实现¶
var topKFrequent = function(nums, k) {
let map = {};
let pq = new PriorityQueue(k, (a, b) => map[a] - map[b] < 0);
for(let i = 0; i < nums.length; i++) {
if(!map[nums[i]]) map[nums[i]] = 1;
else map[nums[i]] = map[[nums[i]]] + 1;
}
let arr = Array.from(new Set(nums));
for(let i = 0; i < arr.length; i++) {
pq.enqueue(arr[i]);
}
return pq.maxHeap.data;
};
合并 K 个排序链表¶
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
示例:
输入:
[
1->4->5,
1->3->4,
2->6
]
输出: 1->1->2->3->4->4->5->6
这一题我们之前在链表篇实现过，殊不知，它也可以利用优先队列完美解决。
来源: LeetCode第23题
/**
* @param {ListNode[]} lists
* @return {ListNode}
*/
var mergeKLists = function(lists) {
let dummyHead = p = new ListNode();
// 定义优先级的函数，重要！
let pq = new PriorityQueue(lists.length, (a, b) => a.val <= b.val);
// 将头结点推入优先队列
for(let i = 0; i < lists.length; i++)
if(lists[i]) pq.enqueue(lists[i]);
// 取出值最小的节点，如果 next 不为空，继续推入队列
while(pq.getSize()) {
let min = pq.dequeue();
p.next = min;
p = p.next;
if(min.next) pq.enqueue(min.next);
}
return dummyHead.next;
};