【Python】優先度付きキューの使い方【heapq】【ABC141 D】 - Qiita

はじめに 今回はPythonの優先度付きキューについてまとめます。 AtCoderのPython3.4.3と3.8で動作確認済みです。 優先度付きキューについて 優先度付きキュー (Priority queue) はデータ型の一つで、具体的には 最小値（最大値）を $O(\log{N})$で取り出す 要素を $O(\log{N})$ で挿入する ことが出来ます。通常のリストだとそれぞれ $O(N)$ ですので高速です。 「リストの要素の挿入」と「最小値（最大値）を取り出す」ことを繰り返すような時に使います。 Pythonでの使い方 Pythonでは優先度付きキューは heapq として標準ライブラリに用意されています。使いたいときはimportしましょう。 各メソッドについて 頻繁に使うメソッドは3つです。 heapq.heapify(リスト)でリストを優先度付きキューに変換。 heapq

[udzura]

なるほど