Python 標準ライブラリ heapq ヒープキュー

ヒープキューを実装したライブラリです。

heapq ヒープキューの使い方

import heapq

h = []

# heappush(heap, item) ヒープに要素を追加
heapq.heappush(h, 5)
heapq.heappush(h, 1)
heapq.heappush(h, 7)
heapq.heappush(h, 2)
heapq.heappush(h, 3)
heapq.heappush(h, 4)
heapq.heappush(h, 8)
heapq.heappush(h, 9)
heapq.heappush(h, 6)
h # => [1, 2, 4, 5, 3, 7, 8, 9, 6]

# heappop(heap) 最小要素のポップ
item = heapq.heappop(h)
item # => 1
h # => [2, 3, 4, 5, 6, 7, 8, 9]

# heappushpop(heap, item) プッシュしてからポップ
item = heapq.heappushpop(h, 5)
item # => 2
h # => [3, 5, 4, 5, 6, 7, 8, 9]

# heapreplace(heap, item) ポップしてからプッシュ
item = heapq.heapreplace(h, 1)
item # => 3
h # => [1, 5, 4, 5, 6, 7, 8, 9]

# nlargest(n, iterable, key=None) 大きいものn個のリスト
heapq.nlargest(3, h) # => [9, 8, 7]
heapq.nlargest(3, 'abcdefgFEDCBA') # => ['g', 'f', 'e']
heapq.nlargest(3, 'abcdefgFEDCBA', str.lower) # => ['g', 'f', 'F']

# nsmallest(n, iterable, key=None) 小さいものn個のリスト
heapq.nsmallest(3, h) # => [1, 4, 5]
heapq.nsmallest(3, 'abcdefgFEDCBA') # => ['A', 'B', 'C']
heapq.nsmallest(3, 'abcdefgFEDCBA', str.lower) # => ['a', 'A', 'b']

# heapify(x) リストをヒープに変換
li = [7,8,9,1,2,3,4,5,6]
heapq.heapify(li)
li # => [1, 2, 3, 5, 7, 9, 4, 8, 6]

# merge(*iterables, key=None, reverse=False) 複数のイテレータを受け取りソートしたイテレータを取得
items1 = [(1, 'A1'), (3, 'A3'), (5, 'A5'), (7, 'A7')]
items2 = [(1, 'B1'), (2, 'B3'), (5, 'B5'), (6, 'B7')]
list(heapq.merge(items1,items2))
# => [(1, 'A1'), (1, 'B1'), (2, 'B3'), (3, 'A3'), (5, 'A5'), (5, 'B5'), (6, 'B7'), (7, 'A7')]

items1.sort(reverse=True)
items2.sort(reverse=True)
list(heapq.merge(items1,items2, reverse=True))
# => [(7, 'A7'), (6, 'B7'), (5, 'B5'), (5, 'A5'), (3, 'A3'), (2, 'B3'), (1, 'B1'), (1, 'A1')]