ヒープと優先度キュー

ヒープとは何ですか?

ヒープは、すべての親がヒープ プロパティ、つまり子よりも常に小さい (min-heap) か、常に大きい (max-heap) のいずれかを満たしている完全なバイナリ ツリーです。 「完了」とは、おそらく最後のレベルを除いて、すべてのレベルがいっぱいであることを意味し、左から右に埋められます。

       1            Min-heap
      / \
     3   5
    / \
   7   4

これは完全なので、フラット配列に保存します。ポインターは必要ありません。インデックス i の場合: 左の子 = 2i + 1、右の子 = 2i + 2、親 = (i - 1) // 2。

最小ヒープと最大ヒープ

|プロパティ |最小ヒープ |最大ヒープ | |----------|----------|----------| |ルート |最小要素 |最大の要素 | |親≤子供? | ✅ はい | ❌ いいえ (≧) | |抽出すると |最小 |最大 |

Python の heapq は、デフォルトでは 最小ヒープ です。最大ヒープの場合、挿入時に値を否定し、抽出時に再度否定します。

挿入と抽出 - ステップバイステップ

挿入 - 最後まで押してからバブルアップ (小さいうちに親と入れ替えます):

import heapq
h = [1, 3, 5, 7]
heapq.heappush(h, 2)  # h becomes [1, 2, 5, 7, 3]

最小の抽出 - ルートを最後の要素と交換し、最後にポップし、下に移動 (より小さい子と交換):

smallest = heapq.heappop(h)  # returns 1

木の高さは log n であるため、両方の操作は O(log n) で実行されます。

Heapify - O(n) でヒープを構築する

heapq.heapify(arr) を呼び出すと、リストは O(n log n) ではなく O(n) で インプレース ヒープに変換されます。これはボトムアップで機能し、各非リーフ ノードをふるい分けします。これは、CS における最も驚くべき複雑さの結果の 1 つです。

優先キューの抽象化

優先キューを使用すると、常に最も優先度の高い項目に最初にアクセスできます。挿入と抽出の両方が O(log n) であるため、ヒープは頼りになる実装です。 「これまでで最高のアイテムをください」というときにいつでも使用してください。