Python WebAcademy

User
<一覧に戻る

最小ヒープと最大ヒープの実装

ヒープは、完全二分木の一種であり、特に優先度キューの実装において重要な役割を果たします。ヒープには主に最小ヒープと最大ヒープの2種類があります。最小ヒープでは親ノードが子ノードよりも小さい値を持ち、最大ヒープでは親ノードが子ノードよりも大きい値を持ちます。この教材では、Pythonを使用して最小ヒープと最大ヒープを実装します。

ヒープの基本操作

ヒープの基本操作には、以下のものがあります。

  • 挿入: 新しい要素をヒープに追加します。
  • 削除: ヒープのルート（最小または最大の値）を削除します。
  • ヒープ化: ヒープの特性を保つために、ノードの位置を調整します。

最小ヒープの実装

以下に最小ヒープの実装を示します。

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

    def insert(self, val):
        self.heap.append(val)
        self._heapify_up(len(self.heap) - 1)

    def remove_min(self):
        if len(self.heap) == 0:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()

        min_val = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        return min_val

    def _heapify_up(self, index):
        parent_index = (index - 1) // 2
        if index > 0 and self.heap[index] < self.heap[parent_index]:
            self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
            self._heapify_up(parent_index)

    def _heapify_down(self, index):
        smallest = index
        left_child_index = 2 * index + 1
        right_child_index = 2 * index + 2

        if left_child_index < len(self.heap) and self.heap[left_child_index] < self.heap[smallest]:
            smallest = left_child_index
        if right_child_index < len(self.heap) and self.heap[right_child_index] < self.heap[smallest]:
            smallest = right_child_index

        if smallest != index:
            self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
            self._heapify_down(smallest)

    def peek(self):
        return self.heap[0] if self.heap else None

    def is_empty(self):
        return len(self.heap) == 0

コードの解説

  1. クラス定義: MinHeap クラスを定義しています。このクラスはリスト heap を持ち、ヒープの要素を格納します。
  2. 挿入メソッド: insert メソッドでは、新しい値をヒープに追加し、ヒープの特性を維持するために _heapify_up メソッドを呼び出します。
  3. 削除メソッド: remove_min メソッドでは、最小値を削除し、ヒープの最後の要素をルートに移動し、ヒープの特性を維持するために _heapify_down メソッドを呼び出します。
  4. ヒープ化メソッド: _heapify_up と _heapify_down メソッドは、挿入または削除後にヒープの特性を維持するためにノードの位置を調整します。
  5. ピークメソッド: peek メソッドは、ヒープの最小値を返しますが、削除はしません。
  6. 空チェックメソッド: is_empty メソッドは、ヒープが空かどうかを判定します。

最大ヒープの実装

次に、最大ヒープの実装を示します。

class MaxHeap:
    def __init__(self):
        self.heap = []

    def insert(self, val):
        self.heap.append(val)
        self._heapify_up(len(self.heap) - 1)

    def remove_max(self):
        if len(self.heap) == 0:
            return None
        if len(self.heap) == 1:
            return self.heap.pop()

        max_val = self.heap[0]
        self.heap[0] = self.heap.pop()
        self._heapify_down(0)
        return max_val

    def _heapify_up(self, index):
        parent_index = (index - 1) // 2
        if index > 0 and self.heap[index] > self.heap[parent_index]:
            self.heap[index], self.heap[parent_index] = self.heap[parent_index], self.heap[index]
            self._heapify_up(parent_index)

    def _heapify_down(self, index):
        largest = index
        left_child_index = 2 * index + 1
        right_child_index = 2 * index + 2

        if left_child_index < len(self.heap) and self.heap[left_child_index] > self.heap[largest]:
            largest = left_child_index
        if right_child_index < len(self.heap) and self.heap[right_child_index] > self.heap[largest]:
            largest = right_child_index

        if largest != index:
            self.heap[index], self.heap[largest] = self.heap[largest], self.heap[index]
            self._heapify_down(largest)

    def peek(self):
        return self.heap[0] if self.heap else None

    def is_empty(self):
        return len(self.heap) == 0

コードの解説

  1. クラス定義: MaxHeap クラスを定義し、最小ヒープと同様にリスト heap を持ちます。
  2. 挿入メソッド: insert メソッドで新しい値を追加し、 _heapify_up メソッドを呼び出します。
  3. 削除メソッド: remove_max メソッドでは、最大値を削除し、最後の要素をルートに移動し、 _heapify_down メソッドを呼び出します。
  4. ヒープ化メソッド: _heapify_up と _heapify_down メソッドは、ヒープの特性を保つためにノードの位置を調整します。
  5. ピークメソッド: peek メソッドは最大値を返します。
  6. 空チェックメソッド: is_empty メソッドは、ヒープが空かどうかを判定します。

使用例

このヒープの実装を使用してみましょう。

# 最小ヒープの使用例
min_heap = MinHeap()
min_heap.insert(3)
min_heap.insert(1)
min_heap.insert(2)

print(min_heap.peek())  # 1
print(min_heap.remove_min())  # 1
print(min_heap.peek())  # 2

# 最大ヒープの使用例
max_heap = MaxHeap()
max_heap.insert(3)
max_heap.insert(1)
max_heap.insert(2)

print(max_heap.peek())  # 3
print(max_heap.remove_max())  # 3
print(max_heap.peek())  # 2

コードの解説

  1. 最小ヒープのインスタンスを作成: MinHeap クラスのインスタンスを作成し、いくつかの値を挿入します。
  2. 最小値の取得と削除: peek メソッドで最小値を取得し、remove_min メソッドで最小値を削除します。
  3. 最大ヒープのインスタンスを作成: MaxHeap クラスのインスタンスを作成し、同様の操作を行います。

以上で、最小ヒープと最大ヒープの実装とその使用例についての説明を終わります。ヒープの理解を深めることで、より高度なデータ構造やアルゴリズムに挑戦する準備が整います。

前に戻る 一覧に戻る

出力結果：