最小堆python

最小堆是一種特殊的樹形數據結構，它的主要特性是每個父節點的值都小於或等於其子節點的值。下面是一個簡單的Python實現最小堆的例子：

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

    def parent(self, i):
        return (i - 1) // 2

    def leftChild(self, i):
        return 2 * i + 1

    def rightChild(self, i):
        return 2 * i + 2

    def insert(self, value):
        self.heap.append(value)
        i = len(self.heap) - 1
        while i != 0 and self.heap[self.parent(i)] > self.heap[i]:
            self.heap[i], self.heap[self.parent(i)] = (
                self.heap[self.parent(i)],
                self.heap[i]
            )
            i = self.parent(i)

    def deleteMin(self):
        if len(self.heap) == 0:
            return None
        root = self.heap[0]
        if len(self.heap) > 1:
            self.heap[0] = self.heap[-1]
            del self.heap[-1]
        else:
            del self.heap[0]
        self.__heapify_up(0)
        return root

    def __heapify_up(self, i):
        while i != 0 and self.heap[i] < self.heap[self.parent(i)]:
            self.heap[i], self.heap[self.parent(i)] = (
                self.heap[self.parent(i)],
                self.heap[i]
            )
            i = self.parent(i)

使用這個類，你可以創建一個最小堆，並插入和刪除元素。例如：

h = MinHeap()
h.insert(3)
h.insert(5)
h.insert(1)
h.insert(2)
print(h.heap)  # Output: [1, 2, 3, 5] (堆的初始狀態)
min_val = h.deleteMin()  # min_val = 1, heap after deletion = [2, 3, 5]
print(min_val)  # Output: 1

這個類只是一個簡單的實現，並沒有包含一些錯誤檢查或最佳化。在實際使用中，你可能需要根據你的需求進行修改或擴展。