はじめに

こんにちは！今回はPythonで「最大ヒップ(Max Heap)」を実装し、ヒープ操作の基本である挿入(add)と削除(delete)の方法を紹介します。ヒープはデータ楮のひとつで、特に、優先度付きキューやソートアルゴリズムに使われる重要な概念です。

ヒープとは？

ヒープは「完全二分木」という構造で表現されるデータ構造です。今回扱う最大ヒープ(Max Heap)では、親ノードの値が常に子ノードの値以上であることが条件になります。
つまり、ルート(最上位)の要素が常にヒープ内で最大値となります。

実装コード

以下は、Pythonで最大ヒープを構築するためのクラスMax Heapの実装です。メソッドごとの説明も加えています。

class MaxHeap:
    def __init__(self, initial_values=None):
        """ ヒープを初期化。初期値が指定されている場合はすべてヒープに追加する """
        self.heap = []
        if initial_values:
            for value in initial_values:
                self.add_heap(value)

    def add_heap(self, value):
        """ ヒープに新しい値を追加し、ヒープ条件を満たすよう調整する """
        self.heap.append(value)  # 値を末尾に追加
        self._heapify_up(len(self.heap) - 1)  # 上方向に調整

    def delete_heap(self):
        """ ヒープのルート（最大値）を削除し、ヒープ条件を満たすよう調整する """
        if len(self.heap) == 0:
            raise IndexError("空のヒープからは削除できません")
        if len(self.heap) == 1:
            return self.heap.pop()
        root_value = self.heap[0]
        self.heap[0] = self.heap.pop()  # 末尾の要素をルートに移動
        self._heapify_down(0)  # 下方向に調整
        return root_value

    def _heapify_up(self, index):
        """ 新しく追加された要素を適切な位置まで上方向に調整する """
        parent_index = (index - 1) // 2
        while index > 0 and self.heap[index] > self.heap[parent_index]:
            self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
            index = parent_index
            parent_index = (index - 1) // 2

    def _heapify_down(self, index):
        """ ルート要素を適切な位置まで下方向に調整する """
        child_index = 2 * index + 1
        while child_index < len(self.heap):
            right_child_index = child_index + 1
            if right_child_index < len(self.heap) and self.heap[right_child_index] > self.heap[child_index]:
                child_index = right_child_index
            if self.heap[index] >= self.heap[child_index]:
                break
            self.heap[index], self.heap[child_index] = self.heap[child_index], self.heap[index]
            index = child_index
            child_index = 2 * index + 1

実行例

次に、実際にMax Heapクラスを使ってヒープを操作してみます。初期値として[6,4,2,1]を持つヒープに対し、次の操作を順番に行います。

新しい値を追加(add_heap)
最大値を削除(delete_heap)

heap = MaxHeap([6, 4, 2, 1])
print("初期ヒープ:", heap.heap)

operations = [7, 8, 5, "delete", 4, 6, 9, "delete", "delete"]

print(f"\t\t\t     i :  {'  '.join(list(map(str, range(9))))}")
for i, operation in enumerate(operations, 1):
    if operation == "delete":
        max_value = heap.delete_heap()
        print(f"{i}. delete_heap(H) \t-> H[i]: {heap.heap} \t-> {max_value}")
    else:
        heap.add_heap(operation)
        print(f"{i}. add_heap(H, {operation}) \t-> H[i]: {heap.heap}")

実行結果

初期ヒープ: [6, 4, 2, 1]
			     i :  0  1  2  3  4  5  6  7  8
1. add_heap(H, 7) 	-> H[i]: [7, 6, 2, 1, 4]
2. add_heap(H, 8) 	-> H[i]: [8, 6, 7, 1, 4, 2]
3. add_heap(H, 5) 	-> H[i]: [8, 6, 7, 1, 4, 2, 5]
4. delete_heap(H) 	-> H[i]: [7, 6, 5, 1, 4, 2] 	-> 8
5. add_heap(H, 4) 	-> H[i]: [7, 6, 5, 1, 4, 2, 4]
6. add_heap(H, 6) 	-> H[i]: [7, 6, 5, 6, 4, 2, 4, 1]
7. add_heap(H, 9) 	-> H[i]: [9, 7, 5, 6, 4, 2, 4, 1, 6]
8. delete_heap(H) 	-> H[i]: [7, 6, 5, 6, 4, 2, 4, 1] 	-> 9
9. delete_heap(H) 	-> H[i]: [6, 6, 5, 1, 4, 2, 4] 	-> 7

コードの説明

add_heap メソッド
値をヒープに追加し、ヒープ条件を満たすように「上方向」に要素を調整します。
delete_heap メソッド
ルート要素(最大値)を削除し、末尾の要素をルートに移動してから「下方向」に要素を調整します。

まとめ

今回のプログラムは、最大ヒープをPythonで実装し、その基本的な操作であるaddとdeleteを紹介しました。ヒープソートや優先度付きキューなど、ヒープはさまざまなアルゴリズムで活用される重要なデータ構造です。最後まで読んでくださり、ありがとうございました。もし改善点や質問があれば、ぜひコメントしてください！