最小堆代碼

最小堆（Min Heap）是一種二叉堆，其中每一個父節點的值都不會大於其子節點的值。最小堆可以用來實作優先佇列，並且可以透過Heap類別來實作。以下是一個最小堆的Python實作範例：

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

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

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

    def build_heap(self, array):
        self.heap = array
        for i in range(len(self.heap) // 2 - 1, -1, -1):
            self.sift_down(i)

    def sift_down(self, i):
        while i * 2 + 1 < len(self.heap):
            j = 2 * i + 1
            if j < len(self.heap) - 1 and self.heap[j] > self.heap[j + 1]:
                j += 1
            if self.heap[i] <= self.heap[j]:
                break
            self.swap(i, j)
            i = j

    def sift_up(self, i):
        while i // 2 > 0:
            if self.heap[i] <= self.heap[i // 2]:
                break
            self.swap(i, i // 2)
            i = i // 2

    def swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def insert(self, item):
        self.heap.append(item)
        self.sift_up(len(self.heap) - 1)

    def extract_min(self):
        if self.is_empty():
            return None
        min_val = self.heap[0]
        self.heap[0] = self.heap[-1]
        self.heap.pop()
        self.sift_down(0)
        return min_val

    def decrease_key(self, i, val):
        self.heap[i] = val
        while i > 0 and self.heap[i // 2] > self.heap[i]:
            self.swap(i, i // 2)
            i = i // 2

    def increase_key(self, i, val):
        self.heap[i] = val
        while i < len(self.heap) // 2 and self.heap[i] < self.heap[i * 2 + 1]:
            self.swap(i, i * 2 + 1)
            i = i * 2 + 1

    def __str__(self):
        return str(self.heap)

heap = Heap()
heap.build_heap([4, 1, 3, 16, 9, 10])
print(heap)
print(heap.extract_min())
print(heap)
heap.insert(7)
print(heap)
heap.decrease_key(2, 2)
print(heap)

這個程式碼實作了一個最小堆，並提供了一些基本操作，如建立最小堆、插入元素、提取最小元素、減少元素值和增加元素值。你可以根據需要修改這些操作。