24. JavaScriptでPriority Queueを実装する

優先度付きキュー(Priority Queue) はアルゴリズム問題に置いてよく利用される抽象データ型です。特にTop-k問題では全体的にソート省けるのでとてもいいアプローチである。

けどJavaScriptにはビルトインのPriority Queueがない。面接時時間ないから、面接官に「仮にPriority Queueがあるとする」と話しといた方がおすすめです。

ここは練習のためで、Priority Queueを実装してください！

class PriorityQueue {
  // 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だけ残る