概念
最大堆是一种完全二叉树，父节点的值总是大于或等于其子节点的值。通常，最大堆可以用数组来实现。
最大堆的主要操作包括插入元素和提取最大值。在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) // 2def _left_child(self, i):return 2 * i + 1def _right_child(self, i):return 2 * i + 2def _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 = parentdef _heapify_down(self, i):max_index = in = 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 = leftif right < n and self.heap[right] > self.heap[max_index]:max_index = rightif max_index != i:self._swap(i, max_index)i = max_indexelse:breakdef _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 Nonemax_val = self.heap[0]last = self.heap.pop()if self.heap:self.heap[0] = lastself._heapify_down(0)return max_valdef get_max(self):return self.heap[0] if self.heap else Nonedef 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
