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

始终思考更好的解决办法

(1)
(70)