堆基本操作实现最大堆

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

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

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

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

    def has_parent(self, i):
        return self.parent(i) >= 0

    def has_left_child(self, i):
        return self.left_child(i) < len(self.heap)

    def has_right_child(self, i):
        return self.right_child(i) < len(self.heap)

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

    def insert(self, key):
        self.heap.append(key)
        self.heapify_up(len(self.heap) - 1)

    def heapify_up(self, index):
        while self.has_parent(index) and self.heap[self.parent(index)] < self.heap[index]:
            self.swap(self.parent(index), index)
            index = self.parent(index)

    def get_max(self):
        if not self.heap:
            raise IndexError("Heap is empty")
        return self.heap[0]

    def extract_max(self):
        if not self.heap:
            raise IndexError("Heap is empty")
        if len(self.heap) == 1:
            return self.heap.pop()
        max_value = self.heap[0]
        self.heap[0] = self.heap.pop()
        self.heapify_down(0)
        return max_value

    def heapify_down(self, index):
        largest = index
        left = self.left_child(index)
        right = self.right_child(index)

        if self.has_left_child(index) and self.heap[left] > self.heap[largest]:
            largest = left

        if self.has_right_child(index) and self.heap[right] > self.heap[largest]:
            largest = right

        if largest != index:
            self.swap(index, largest)
            self.heapify_down(largest)

# 示例使用
max_heap = MaxHeap()
max_heap.insert(3)
max_heap.insert(2)
max_heap.insert(15)
max_heap.insert(5)
max_heap.insert(4)
max_heap.insert(45)

print("Max value:", max_heap.get_max())  # 输出最大值
print("Extracted max:", max_heap.extract_max())  # 移除并返回最大值
print("New max value:", max_heap.get_max())  # 查看新的最大值

这段代码定义了一个最大堆的实现，包含基本的插入、获取最大值、移除最大值并重新堆化等操作。最大堆是一种经典的优先队列实现方式，其中父节点的值总是大于或等于其子节点的值。