24. 用JavaScript手写一个Priority Queue
分享给更多人
中等难度 -通过 / -执行
优先队列(Priority Queue) 是在算法题目中经常用到的数据结构。特别是Top-k系列问题非常有效,因为它可以避免整体的排序。
JavaScript中没有原生的优先队列。在真实的面试中,你可以告诉面试官说“假设我们已经又一个优先队列的实现我可以直接使用”,因为没有时间让我们去手写一个优先队列。
但是这不妨碍优先队列成为一个很好的联手题目,所以请手写一个优先队列!
class PriorityQueue {
// 构造函数接受一个compare函数
// compare返回的-1, 0, 1决定元素是否优先被去除
constructor(compare) {
}
// 添加一个元素
add(element) {
}
// 去除头元素并返回
poll() {
}
// 取得头元素
peek() {
}
// 取得元素数量
size() {
}
}
以下的例子可能更好理解
const pq = new PriorityQueue((a, b) => a - b)
// (a, b) => a - b 意味着更小的元素排序更靠前
// 所以最小的元素首先被去除
pq.add(5)
// 5是唯一元素
pq.add(2)
// 2被添加
pq.add(1)
// 1被添加
pq.peek()
// 因为小元素靠前,这里返回1
pq.poll()
// 1
// 1 被去除,剩下2和5
pq.peek()
// 2,此时2是最小
pq.poll()
// 2
// 2被去除,剩下了5