heap
pythonではheapqクラスのメソッドにlist型のデータを渡して、直接編集する
1. basic
2. heappush
python ソースコード
import heapq
l = [3, 10, 5, 9, 1, 2]
print(l)
# heapで並べ替える
heapq.heapify(l)
print(l)
# heapで追加する
heapq.heappush(l, 0)
print(l)
# heapで追加する
heapq.heappush(l, 4)
print(l)
python 出力結果
[3, 10, 5, 9, 1, 2]
[1, 3, 2, 9, 10, 5] ★heapなので、先頭以外は保証されない
[0, 3, 1, 9, 10, 5, 2] ★heapなので、先頭以外は保証されない
^
[0, 3, 1, 4, 10, 5, 2, 9] ★heapなので、先頭以外は保証されない
^
3. heappop
- 先頭を取り出す
python ソースコード
import heapq
l = [3,10,5, 9, 1, 2]
print(l)
# heapで並べ替える
heapq.heapify(l)
print(l)
# heapで先頭を取得する
print(heapq.heappop(l))
print(l)
# heapで先頭を取得する
print(heapq.heappop(l))
print(l)
python 出力結果
[3, 10, 5, 9, 1, 2]
[1, 3, 2, 9, 10, 5] ★heapなので、先頭以外は保証されない
1
[2, 3, 5, 9, 10] ★heapなので、先頭以外は保証されない
2
[3, 9, 5, 10] ★heapなので、先頭以外は保証されない
4. ksmallest
- 指定された最小値を取り出す
ksmallest(取得数, heapリスト)で指定するk + smallの最上級で覚える- 第一引数に取得数を指定することに注意
python ソースコード
import heapq
l = [3,10,5, 9, 1, 2]
print(l)
# heapで並べ替える
heapq.heapify(l)
print(l)
# 最小値３つを取り出す
print(heapq.nsmallest(3,l))
print(l)
python 出力結果
[3, 10, 5, 9, 1, 2]
[1, 3, 2, 9, 10, 5]
[1 2, 3] ★最小値３つを取得
[1, 3, 2, 9, 10, 5] ★ksmallestでは元のheapリストは変更されない
5. klargest
- 指定された最小値を取り出す
klargest(取得数, heapリスト)で指定するk + largeの最上級で覚える- 第一引数に取得数を指定することに注意
python ソースコード
import heapq
l = [3,10,5, 9, 1, 2]
print(l)
# heapで並べ替える
heapq.heapify(l)
print(l)
# 最大値4つを取り出す
print(heapq.nlargest(4,l))
print(l)
python 出力結果
[3, 10, 5, 9, 1, 2]
[1, 3, 2, 9, 10, 5]
[10, 9, 5, 3] ★最大値４つ
[1, 3, 2, 9, 10, 5] ★klargestでは元のheapリストは変更されない
6. 発展編
6.1. ２次元リストを渡した場合
- 第一引数でソートされる