数据结构：python实现最大堆算法

概念

最大堆是一种完全二叉树，父节点的值总是大于或等于其子节点的值。通常，最大堆可以用数组来实现。

最大堆的主要操作包括插入元素和提取最大值。在Python中，可以用一个列表来存储堆的元素。索引从0开始的话，父节点和子节点的位置关系需要确定。对于索引i的节点，其左子节点是2i+1，右子节点是2i+2，父节点则是(i-1)//2。

插入元素时，需要将新元素添加到数组的末尾，然后进行上浮操作（percolate up），也就是不断和父节点比较，如果比父节点大就交换位置，直到满足最大堆的性质。这样保证插入后堆仍然正确。

提取最大值的操作通常是取出堆顶元素（即数组的第一个元素），然后将数组的最后一个元素移到堆顶，接着进行下沉操作（percolate down），也就是与左右子节点中较大的那个比较，如果比子节点小就交换，直到满足堆的性质。

编写代码的大致步骤：
1.定义MaxHeap类，初始化时可能有输入的数组，并构建堆。
2.实现插入方法，把元素添加到列表末尾，然后上浮。
3.实现提取最大值的方法，交换首尾元素，弹出最后一个，然后下沉新的首元素。
4.编写上浮和下沉的辅助方法。
5.编写构建堆的方法，比如使用下沉操作从最后一个非叶子节点开始调整。

以下是使用Python实现的最大堆（Max Heap）算法：

class MaxHeap:
    def __init__(self, arr=None):
        self.heap = []
        if arr is not None:
            self.heap = arr.copy()
            self._build_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 _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def _heapify_up(self, i):
        while i > 0 and self.heap[i] > self.heap[self._parent(i)]:
            parent = self._parent(i)
            self._swap(i, parent)
            i = parent

    def _heapify_down(self, i):
        max_index = i
        n = len(self.heap)
        
        while True:
            left = self._left_child(i)
            right = self._right_child(i)
            
            if left < n and self.heap[left] > self.heap[max_index]:
                max_index = left
            if right < n and self.heap[right] > self.heap[max_index]:
                max_index = right
                
            if max_index != i:
                self._swap(i, max_index)
                i = max_index
            else:
                break

    def _build_heap(self):
        n = len(self.heap)
        start = n // 2 - 1  # 最后一个非叶子节点
        for i in range(start, -1, -1):
            self._heapify_down(i)

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

    def extract_max(self):
        if not self.heap:
            return None
        max_val = self.heap[0]
        last = self.heap.pop()
        if self.heap:
            self.heap[0] = last
            self._heapify_down(0)
        return max_val

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

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

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

# 示例用法
if __name__ == "__main__":
    # 测试插入和提取操作
    heap = MaxHeap()
    heap.insert(3)
    heap.insert(1)
    heap.insert(4)
    heap.insert(9)
    heap.insert(2)
    
    print("Extracting max values:")
    while not heap.is_empty():
        print(heap.extract_max(), end=" ")  # 应该输出：9 4 3 2 1
    
    # 测试通过数组初始化
    print("\n\nTesting array initialization:")
    arr = [3, 1, 4, 9, 2]
    heap_from_array = MaxHeap(arr)
    print("Original array:", arr)
    print("Heap structure:", heap_from_array.heap)
    print("Extracting max values:")
    while not heap_from_array.is_empty():
        print(heap_from_array.extract_max(), end=" ")  # 应该输出：9 4 3 2 1