Priority Queue is a commonly used data structure in algorithm problem. Especially useful for Top K problem with a huge amount of input data, since it could avoid sorting the whole but keep a fixed-length sorted portion of it.

Since there is no built-in Priority Queue in JavaScript, in a real interview, you should tell interview saying that "Suppose we already have a Priority Queue Class I can use", there is no time for you to write a Priority Queue from scratch.

But it is a good coding problem to practice, so please implement a Priority Queue with following interface

class PriorityQueue {  // compare is a function defines the priority, which is the order  // the elements closer to first element is sooner to be removed.  constructor(compare) {    }    // add a new element to the queue  // you need to put it in the right order  add(element) {  }  // remove the head element and return  poll() {    }  // get the head element  peek() {  }  // get the amount of items in the queue  size() {  }}

Here is an example to make it clearer

const pq = new PriorityQueue((a, b) => a - b)// (a, b) => a - b means// smaller numbers are closer to index:0// which means smaller number are to be removed soonerpq.add(5)// now 5 is the only elementpq.add(2)// 2 addedpq.add(1)// 1 addedpq.peek()// since smaller number are sooner to be removed// so this gives us 1pq.poll()// 1 // 1 is removed, 2 and 5 are leftpq.peek()// 2 is the smallest now, this returns 2pq.poll()// 2 // 2 is removed, only 5 is left

讨论 (91)