Python3 - ヒープ

ヒープはノードに常に子供が2個あって、子供より親は小さい値を持ちます。ヒープは配列で表せます。配列の0番目は一番上の根ノードです。あとは、k番目のノードの子供は、左が2k+1、右が2k+2番目になります。挿入は最後に挿入して、親ノードと比較して必要に応じて交換することを繰り返します。

Python3にはヒープのデータ構造がデフォルトで用意されているようなので、使ってみます。heapqです。これはヒープキュー、優先度キュー、プライオリティキューとかいわれるものみたいで、「優先度が高い順に取り出せるデータ構造」だそうです。（参考：優先度キュー）

普通の配列をヒープにする

コード

h = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
hq.heapify(h)
print(h)

結果

[0, 1, 4, 2, 6, 5, 8, 3, 7, 9, 10]

コード

h = [10, 5, 12, 43, 1, 30, 45, 12, 14, 15, 43, 53]
hq.heapify(h)
print(h)

結果

[1, 5, 12, 12, 10, 30, 45, 43, 14, 15, 43, 53]

ヒープに挿入する

import heapq as hq

h = [
    (5, 'a'),
    (6, 'b'),
    (3, 'c'),
    (1, 'd'),
    (9, 'e')
]
hq.heapify(h)
hq.heappush(h, (7, 'f'))
hq.heappush(h, (2, 'g'))
hq.heappush(h, (2, 'h'))
print(h)

結果

[(1, 'd'), (2, 'h'), (2, 'g'), (5, 'a'), (9, 'e'), (7, 'f'), (3, 'c'), (6, 'b')]

ヒープからpopする

import heapq as hq

h = [
    (5, 'a'),
    (6, 'b'),
    (3, 'c'),
    (1, 'd'),
    (9, 'e')
]
hq.heapify(h)
hq.heappush(h, (7, 'f'))
hq.heappush(h, (2, 'g'))
hq.heappush(h, (4, 'h'))
print(h)
print('--- heappop ---')
print(hq.heappop(h))
print(h)
print('--- heappushpop ---')
print(hq.heappushpop(h, (1, 'i')))
print(h)
print('--- heapreplace ---')
print(hq.heapreplace(h, (1, 'j')))
print(h)

結果

[(1, 'd'), (4, 'h'), (2, 'g'), (5, 'a'), (9, 'e'), (7, 'f'), (3, 'c'), (6, 'b')]
--- heappop ---
(1, 'd')
[(2, 'g'), (4, 'h'), (3, 'c'), (5, 'a'), (9, 'e'), (7, 'f'), (6, 'b')]
--- heappushpop ---
(1, 'i')
[(2, 'g'), (4, 'h'), (3, 'c'), (5, 'a'), (9, 'e'), (7, 'f'), (6, 'b')]
--- heapreplace ---
(2, 'g')
[(1, 'j'), (4, 'h'), (3, 'c'), (5, 'a'), (9, 'e'), (7, 'f'), (6, 'b')]

heappushpopはpushしてから、popする。heappushしてからheappopするよりも効率的だそうです。pushしてからpopするので、pushしたものも含めて最小値をpopします。heapreplaceはpopしてからpushするので、pushした要素が最小値でもpopされません。