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だけ残る