優先度つきキュー(Priority Queue)

概要

• 通常のキューは最初にPushしたアイテムを最初にPopする(FIFO)
• 優先度付きキューの場合、あらかじめ指定した任意の優先度に基づく順番でPopさせることができる
• 優先度はキューにPushされる任意のアイテム2つについて、その二者間に順序付けができるものである
  • e.g. 優先度を値の小さい順とし、空のPriority Queueに 5, 3, 2, 1, 4 をこの順番でPushした後にPopされる順番は 1, 2, 3, 4, 5
• Push/Pop以外にも参照や更新などの実装について言及されることもあるが、ここでは割愛する
• 内部のデータ構造でPush/Popの時間計算量・空間計算量が異なる
• 実装が比較的楽でキューの長さ に対しPush/Popがそれぞれ でできることから、ヒープで実装されているものが多い

実装

ある程度シンプルなPriority QueueをPython3とGoで実装してみる。要件は

• ヒープを持つ
• ヒープへのPush/Popができる
• ヒープは特定の型のみを受け付けるのではなく、ある程度柔軟性を持つ
  • アイテムのデータ型は統一されているものとする。i.e. あるアイテムは整数型で、別のあるアイテムは文字列型、といったことはない
• アイテムに優先度を与えるComparatorを定義できる。Comparatorはアイテムを入力すると整数型の優先度を出力する関数である
• 優先度の値が小さいものからPopされる

Python3で実装する

もともとPython3は型が必須ではないのと、標準でheapqライブラリがあるので適当にComparatorを作ればよい

Powered by OnlineGDB

Goで実装する

Item.Entryの型をinterface{}とすることで型ごとにstructやmethodの定義をしないようにした。 同じことをするのにGoは体感でPython3の3倍くらいのコード量が必要だが、Priority Queueは特に差がめんどくさい部類に入る