ヒープで今の最小値を取る

毎回並べ直す代わりに、最小要素を速く取り出せるデータ構造を使います。すべてがソート順に並んでいるわけではありません。

言語：Python / 計算量：構築 O(N)、追加・削除 O(log N)

前提：ソートで順序を作る

考え方

1. heapq.heapify(a) で既存配列をヒープにします。
2. heappush で追加、heappop で最小を取り出します。
3. a[0]だけが最小保証。途中の添字に順位の意味はありません。

具体例

[5,2,8]から2を取り出し、1を追加すると次に取り出せるのは1です。

実装

import heapq
a=[5,2,8];heapq.heapify(a)
print(heapq.heappop(a))
heapq.heappush(a,1)
print(heapq.heappop(a))

注意する条件

空ヒープからpopするとエラーです。任意の要素の削除が必要なら遅延削除など別の設計が要ります。

確認問題

[5,2,8]の最小値を取り出した後、1を追加。次の最小は？

実装課題

N と正整数列 A。2つの最小値を取り出して和を戻す操作を1つになるまで行う。各和を費用として足した総額。N≤200000。

入力:
3
1 2 3
出力:
9

import heapq
n=int(input());a=list(map(int,input().split()));heapq.heapify(a);ans=0
while len(a)>1:
    s=heapq.heappop(a)+heapq.heappop(a);ans+=s;heapq.heappush(a,s)
print(ans)

読了の記録・下書き・メモへ