优先级队列实际上是二叉堆的一种具体实现。它旨在维护一个具有特定固定结构的队列，以保持整个二叉堆的性质。因此我们需要先了解一下 二叉堆 这个数据结构。
# 什么是二叉堆
二叉堆就是一种能够动态排序的数据结构。所谓动态排序，就是说我们可以不断往数据结构里面添加或删除元素，数据结构会自动调整元素的位置，使得我们可以有序地从数据结构中读取元素，这是一般的排序算法做不到的。
能动态排序的常用数据结构其实只有两个，一个是优先级队列（底层用二叉堆实现），另一个是二叉搜索树。二叉搜索树的用途更广泛，优先级队列能做的事情，二叉搜索树其实都能做。但优先级队列的 API 和代码实现相较于二叉搜索树更简单，所以一般能用优先级队列解决的问题，我们没必要用二叉搜索树。
# 二叉堆的性质
二叉堆可以被直接看作是一个 特殊的二叉树，这棵二叉树上任意节点的值都必须大于等于、小于等于其左右子树所有节点的值。如果是大于等于，那么将其称之为 大顶堆，如果是小于等于，那么将其称之为 小顶堆。
对于小顶堆，每个节点下方的所有节点的值都比它大，那么不难想象根节点就是整棵树上的最小值。同理，大顶堆的根节点就是整棵树上的最大值。所以二叉堆可以辅助我们快速找到最大值或最小值。
因此我们简单来说就是，对这个二叉堆进行 push 和 pop 操作的时候，这个堆都会 自动地在内部调整好自己的结构，最终保持自己是一个有序序列。而调整的过程是封装在内部不可见的，我们相当于是在对一个黑盒进行数据 push 和数据 pop，内部自动调整即可。
# 实际实现：优先级队列
上面也说了，优先级队列是二叉堆这一数据结构的具体代码实现。它主要向外面暴露了几个特殊的 API：
size()：返回队列中的元素个数。push()：增，向堆中插入一个指定值的元素pop()：删，删除并返回队列中的堆顶元素peek()：查，返回队列中的堆顶元素
只用这四个 API，就能够借助它来实现各种复杂的数据操作了。
接下来直接上代码，各种注释实际上写的比较详细了：
/** 优先级队列 */ | |
// 几个关键点： | |
// 1. 使用数组来模拟二叉树： | |
// 主要是时间复杂度的问题。对于其 push 和 pop 方法，第一步都是找到二叉树最底层的最右侧元素。 | |
// 如果使用常规二叉树，要拿到这个节点必须得层序遍历或者递归遍历，时间复杂度退化为 O (n) | |
// 如果使用数组来进行模拟，直接取最后一个元素即可，时间复杂度为 O (1) | |
// 使用数组来进行模拟的前提是这个二叉树必须是完全二叉树，即除了最后一层，其他层的节点都是满的 | |
export class MonoQueue<T> { | |
private heap: T[] | |
private count: number | |
// 比较函数：用以具体指定优先级队列内部的排序规则 | |
// 返回值是经过函数计算的结果，用以判断在指定规则下 a 和 b 的大小 | |
private compare: (a: T, b: T) => number | |
// 构造器创建一个容量为 capacity 的优先级队列，并传入比较函数 compare 用以指定具体的内部排序规则 | |
constructor(capacity: number, compare: (a: T, b: T) => number) { | |
this.heap = new Array(capacity + 1) // + 1 是为了保证索引为 0 的元素不被使用，从 1 开始 | |
this.count = 0 | |
this.compare = compare | |
} | |
// 返回队列中的元素个数 | |
public size() { | |
return this.count | |
} | |
// 根据传进来的节点索引，获取其父节点的索引 | |
private parent(i: number) { | |
return Math.floor(i / 2) | |
} | |
// 根据传进来的节点索引，获取其左子节点的索引 | |
private left(i: number) { | |
return i * 2 | |
} | |
// 根据传进来的节点索引，获取其右子节点的索引 | |
private right(i: number) { | |
return i * 2 + 1 | |
} | |
// 根据传进来的两个节点索引，交换数组对应的两个元素 | |
private swap(i: number, j: number) { | |
;[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]] | |
} | |
// 增，向堆中插入一个值为 val 的元素 | |
public push(val: T) { | |
// 把新元素放在最后 | |
this.heap[++this.count] = val | |
// 然后上浮到正确位置 | |
this.swim(this.count) | |
} | |
// 删，删除并返回队列中的最小元素（堆顶元素） | |
public pop() { | |
const res = this.heap[1] | |
// 把堆底元素放到堆顶 | |
this.heap[1] = this.heap[this.count--] | |
// 然后下沉到正确位置 | |
this.sink(1) | |
return res | |
} | |
// 查，返回队列中的最小元素（堆顶元素） | |
public peek() { | |
// 为了保持索引计算的准确性，索引 0 不会被使用，数据的第一项从 1 开始 | |
return this.heap[1] | |
} | |
/** 优先级队列的核心难点：上浮 */ | |
// 根据传入的索引进行上浮操作，时间复杂度 O (logN)，和树的高度有关 | |
private swim(i: number) { | |
// 1. 不是头节点；2. 它的父节点的值比它自己还要大 | |
// 满足上述两个要求就上浮 | |
while (i > 1 && this.compare(this.heap[this.parent(i)], this.heap[i]) > 0) { | |
this.swap(this.parent(i), i) | |
i = this.parent(i) | |
} | |
} | |
/** 优先级队列的核心难点：下沉 */ | |
// 根据传入的索引进行下沉操作，时间复杂度 O (logN)，和树的高度有关 | |
private sink(i: number) { | |
// 确保左 / 右子节点的索引不超过 heap 的大小 | |
while (this.left(i) <= this.size() || this.right(i) <= this.size()) { | |
let min = i | |
if ( | |
this.left(i) <= this.size() && | |
this.compare(this.heap[this.left(i)], this.heap[min]) < 0 | |
) { | |
min = this.left(i) | |
} | |
if ( | |
this.right(i) <= this.size() && | |
this.compare(this.heap[this.right(i)], this.heap[min]) < 0 | |
) { | |
min = this.right(i) | |
} | |
if (min === i) break | |
this.swap(i, min) | |
i = min | |
} | |
} | |
} |
