ヒープ

ヒープ#

ヒープ（Heap） は、ヒープ条件 を満たす完全二分木ベースのデータ構造。

最小ヒープ（min-heap）: 親ノードの値 ≤ 子ノードの値（根が最小値）
最大ヒープ（max-heap）: 親ノードの値 ≥ 子ノードの値（根が最大値）

ヒープは配列で効率的に表現できる。インデックス \(i\) のノードに対して：

左の子: \(2i + 1\)
右の子: \(2i + 2\)
親: \(\lfloor (i-1)/2 \rfloor\)

主な操作の計算量：

操作	計算量
`push` (挿入)	\(O(\log n)\)
`pop` (最小/最大値取り出し)	\(O(\log n)\)
`peek` (最小/最大値参照)	\(O(1)\)
`heapify` (配列からヒープ構築)	\(O(n)\)

ヒープの操作#

push（挿入）#

末尾に要素を追加する
ヒープ条件を満たすまで親と交換しながら上に移動（sift up / bubble up）

pop（取り出し）#

根（最小/最大値）を取り出す
末尾要素を根に移動する
ヒープ条件を満たすまで子と交換しながら下に移動（sift down / bubble down）

最小ヒープの実装#

class MinHeap:
    def __init__(self):
        self._data = []

    def __len__(self):
        return len(self._data)

    def peek(self):
        if not self._data:
            raise IndexError('heap is empty')
        return self._data[0]

    def push(self, value):
        self._data.append(value)
        self._sift_up(len(self._data) - 1)

    def pop(self):
        if not self._data:
            raise IndexError('heap is empty')
        self._swap(0, len(self._data) - 1)
        value = self._data.pop()
        self._sift_down(0)
        return value

    def _sift_up(self, i):
        while i > 0:
            parent = (i - 1) // 2
            if self._data[i] < self._data[parent]:
                self._swap(i, parent)
                i = parent
            else:
                break

    def _sift_down(self, i):
        n = len(self._data)
        while True:
            smallest = i
            left, right = 2 * i + 1, 2 * i + 2
            if left < n and self._data[left] < self._data[smallest]:
                smallest = left
            if right < n and self._data[right] < self._data[smallest]:
                smallest = right
            if smallest == i:
                break
            self._swap(i, smallest)
            i = smallest

    def _swap(self, i, j):
        self._data[i], self._data[j] = self._data[j], self._data[i]

heap = MinHeap()
for x in [5, 3, 8, 1, 4]:
    heap.push(x)

print('peek:', heap.peek())       # 1
print('pop:', heap.pop())         # 1
print('pop:', heap.pop())         # 3
print('pop:', heap.pop())         # 4
print('内部配列:', heap._data)

peek: 1
pop: 1
pop: 3
pop: 4
内部配列: [5, 8]

heapify — \(O(n)\) でのヒープ構築#

配列の末尾から各内部ノードに sift_down を適用することで、\(O(n)\) でヒープを構築できる。

要素を1つずつ push する \(O(n \log n)\) より効率的。

class MinHeap(MinHeap):
    @classmethod
    def heapify(cls, array):
        h = cls()
        h._data = list(array)
        n = len(h._data)
        # 最後の内部ノードから根に向かって sift_down
        for i in range((n - 2) // 2, -1, -1):
            h._sift_down(i)
        return h


h = MinHeap.heapify([5, 3, 8, 1, 4, 2, 7])
print('内部配列:', h._data)
result = []
while h:
    result.append(h.pop())
print('ソート結果:', result)

内部配列: [1, 3, 2, 5, 4, 8, 7]
ソート結果: [1, 2, 3, 4, 5, 7, 8]

Python の `heapq` モジュール#

Python 標準ライブラリの heapq は最小ヒープを提供する。リストをヒープとして操作する関数群。

import heapq

data = [5, 3, 8, 1, 4]
heapq.heapify(data)        # in-place でヒープ化 O(n)
print('heapify後:', data)

heapq.heappush(data, 0)
print('push(0)後:', data)

print('pop:', heapq.heappop(data))   # 0
print('pop:', heapq.heappop(data))   # 1

heapify後: [1, 3, 8, 5, 4]
push(0)後: [0, 3, 1, 5, 4, 8]
pop: 0
pop: 1

import heapq

data = [5, 3, 8, 1, 4]

# push と pop を同時に行う（ヒープサイズ不変）
heapq.heapify(data)
print('heappushpop(0):', heapq.heappushpop(data, 0))   # 0（新要素が最小なのでそのまま返る）
print('heappushpop(9):', heapq.heappushpop(data, 9))   # 1

# n個の最小/最大値を取得
data = [5, 3, 8, 1, 4, 2, 7]
print('nsmallest(3):', heapq.nsmallest(3, data))   # [1, 2, 3]
print('nlargest(3):', heapq.nlargest(3, data))     # [8, 7, 5]

heappushpop(0): 0
heappushpop(9): 1
nsmallest(3): [1, 2, 3]
nlargest(3): [8, 7, 5]

ヒープソート#

ヒープを利用した比較ベースのソートアルゴリズム。

時間計算量: \(O(n \log n)\)（最悪・平均・最良すべて）
空間計算量: \(O(1)\)（in-place）
安定ソートではない

def heap_sort(arr):
    n = len(arr)

    def sift_down(i, end):
        while True:
            largest = i
            left, right = 2 * i + 1, 2 * i + 2
            if left < end and arr[left] > arr[largest]:
                largest = left
            if right < end and arr[right] > arr[largest]:
                largest = right
            if largest == i:
                break
            arr[i], arr[largest] = arr[largest], arr[i]
            i = largest

    # 最大ヒープを構築
    for i in range((n - 2) // 2, -1, -1):
        sift_down(i, n)

    # 根（最大値）を末尾と交換しながらソート
    for end in range(n - 1, 0, -1):
        arr[0], arr[end] = arr[end], arr[0]
        sift_down(0, end)

    return arr


data = [5, 3, 8, 1, 4, 2, 7]
print(heap_sort(data))

[1, 2, 3, 4, 5, 7, 8]

活用例#

優先度付きキュー: タスクスケジューリング、イベント駆動シミュレーション
ダイクストラ法 / A* 法: 最短経路探索
K番目の最小/最大値: ストリームデータの上位K件管理
外部マージソート: 大容量データのソート

ヒープ

Contents