はじめに
最近。アルゴリズムをまたちょくちょく勉強しています。(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番目に大きい要素
これを使って以下の問題にチャレンジしてみましょう！！！
🙇 ここでは問題のみにしています 🙇