はじめに
こんにちは！今回は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を紹介しました。ヒープソートや優先度付きキューなど、ヒープはさまざまなアルゴリズムで活用される重要なデータ構造です。最後まで読んでくださり、ありがとうございました。もし改善点や質問があれば、ぜひコメントしてください！