Priority Queue

Priority Queueはelementを追加時自動的にソートできる便利なコレクションである。一部のLeetCode問題ではPriority Queueを使わないとタイムアウトが発生する。(e.g. 問題502問題1834問題1962

これからPriority Queueの使い方を紹介します。例えば、今Personというdata classがある。

data class Person(val name: String, val age: Int)

年齢昇順のPriority Queue定義

val queue = PriorityQueue<Person> { p1, p2 -> p1.age - p2.age }

または

val queue = PriorityQueue<Person>(compareBy { it.age })

年齢降順のPriority Queue定義

val queue = PriorityQueue<Person> { p1, p2 -> p2.age - p1.age }

または

val queue = PriorityQueue<Person>(compareByDescending { it.age })

elementの追加

queue.add(Person("Cecil", 18))

先頭elementの取得および削除

val queue = PriorityQueue<Person>(compareByDescending { it.age })
queue.add(Person("Cecil", 18))
queue.add(Person("Eric", 19))
queue.add(Person("Rachit", 17))
val oldestPerson = queue.peek() // Ericを取得、queueの変化なし
val oldestPerson = queue.poll() // Ericを取得、且つqueueからEricが削除される