🗡️

優先度付きキュー heapq

2021/08/08に公開

ABC212のD問題 (不参加だったので精進だけれど) を制限時間内に収めるのに覚えた。

最初は list l に int v を昇順に挿入するために、

import bisect

l = list()
略
l.pop(0)
略
bisect.insert(l, v)

のようにしていたがいくつかの問題で TLE (制限時間 2s をオーバー)。
リストから最小値(先頭要素)を除く部分が遅いかもと思って list の替わりに deque を使って l.popleft() を使用してみても TLE が増えてしまった。
※ pypy で投稿してみても TLE だった。

解説を見ても自分の実装と違うのは「優先度付きキュー」なるものを使っているところだった。
Python の場合は heapq という名の実装があると知り、https://qiita.com/ell/items/fe52a9eb9499b7060ed6 を参考に上記部分を次のように更新したら、いずれの問題も 200ms 前後で AC できた。

import heapq

l = list()
heapq.heapify(l)
略
heapq.heappop(l)
略
heapq.heappush(l, v)

※ l = heapq() とかでないのが不思議。

Discussion