はじめに

最近。アルゴリズムをまたちょくちょく勉強しています。(Pythonで...)
それで使用した、Heap Queueについてまとめました。

概要

ヒープ(heap)とは木構造のうち親が子より常に大きい(小さい)という条件を満たすもの
そしてheapq は 最小ヒープ を扱うためのモジュール
ヒープ構造を使うことでリストから 最小値や最大値を効率的に取得・削除 することが可能

✅ 特徴

二分ヒープ（binary heap） に基づく

最小ヒープ（min-heap） として動作（常に最小値が先頭に来る）

時間計算量：挿入・削除が O(log n)、最小値参照が O(1)

⚙️ 基本操作

1. heap作成と追加

heapq は普通のリストをheapとする。
最初に空リストを用意し、heappush() で要素を追加。

import heapq

heap = []
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)

print(heap)  # [1, 2, 5, 3]

以下importのみは省略...

2. 最小値の取得と削除

heappop()は最小要素を取り出して削除します。
空のヒープから呼び出すとIndexError

heap = [1, 2, 5, 3]
min_value = heapq.heappop(heap)
print(min_value)  # 1
print(heap)       # [2, 3, 5]

3. 最小値の参照のみ

削除せずに最小値を確認（あたりまえ）

print(heap[0])  # 最小値を参照（O(1)）

4. 既存のリストをheap化

heapify()はリストをインプレース（破壊的）にヒープ化します。
時間計算量は O(n)。

nums = [4, 7, 1, 9, 3]
heapq.heapify(nums)
print(nums)  # [1, 3, 4, 9, 7]

⚠️ ここから特殊

5. 追加後に最小を取り出す

heappushpop()はitem をヒープに追加し、その後で最小値を取り出して返す
一度に挿入と削除を行うので、性能が良い

heap = [2, 4, 6]
result = heapq.heappushpop(heap, 1)
print(result)  # 1（追加された1が最小なので即削除）
print(heap)    # [2, 4, 6]

result = heapq.heappushpop(heap, 5)
print(result)  # 2（5を追加後、最小の2を削除）
print(heap)    # [4, 5, 6]

6. 最小を取り出した後に追加

heapreplace()は最小値を取り出して返した後、item を追加する。
heappushpop()とは順序が逆。

heap = [2, 4, 6]

result = heapq.heapreplace(heap, 1)
print(result)  # 2（最小値を削除）
print(heap)    # [1, 4, 6]（1を追加）

7. 大きい順に指定した要素分を取得。

nlargest()はイテラブルから大きい順にn個の要素をリストで返す

heap = [5, 3, 9, 1, 10, 8]
print(heapq.nlargest(3, nums))  # [10, 9, 8]

8. 小さい順に指定した要素分を取得。

nsmallest()はイテラブルから小さい順にn個の要素をリストで返します。

nums = [5, 3, 9, 1, 10, 8]
print(heapq.nsmallest(3, nums))  # [1, 3, 5]

㉄ K番目に大きい要素

これを使って以下の問題にチャレンジしてみましょう！！！

🙇　ここでは問題のみにしています　🙇