### 实现堆化（Heapify）的过程 在Python中，可以利用`heapq`模块来简化最小堆或最大堆的操作。然而，为了展示具体的堆化过程，下面提供了一个不依赖内置函数的手动实现方法。 #### 手动构建最小堆 当需要将一个列表转换成最小堆时，核心操作是从最后一个非叶子节点开始向前遍历每一个节点，并执行下沉操作（也称为percolate down）。如果当前节点大于其任意子节点，则与其较小的那个子节点交换位置；重复这一过程直到满足最小堆性质为止[^1]。 ```python def min_heapify(arr, n, i): smallest = i # Initialize smallest as root l = 2 * i + 1 # left child index r = 2 * i + 2 # right child index # If left child exists and is less than current node if l < n and arr[l] < arr[smallest]: smallest = l # If right child exists and is smaller than the smallest so far if r < n and arr[r] < arr[smallest]: smallest = r # Change root (if needed), then recursively heapify affected subtree if smallest != i: arr[i], arr[smallest] = arr[smallest], arr[i] # swap min_heapify(arr, n, smallest) def build_min_heap(arr): n = len(arr) # Build a min heap from an unordered array. start_index = n // 2 - 1 # Index of last non-leaf node for i in range(start_index, -1, -1): min_heapify(arr, n, i) ``` 上述代码实现了通过调整数组中的元素顺序使其成为合法的最小堆结构的功能。这里定义了两个辅助函数：一个是用于处理单个节点及其后代之间的关系(`min_heapify`)；另一个则是用来初始化整个数据集上的最小堆形态(build_min_heap)。 #### 构建最大堆 同样地，也可以创建一个最大堆版本，在这种情况下只需改变比较条件即可： ```python def max_heapify(arr, n, i): largest = i l = 2 * i + 1 r = 2 * i + 2 if l < n and arr[l] > arr[largest]: largest = l if r < n and arr[r] > arr[largest]: largest = r if largest != i: arr[i], arr[largest] = arr[largest], arr[i] max_heapify(arr, n, largest) def build_max_heap(arr): n = len(arr) start_index = n // 2 - 1 for i in range(start_index, -1, -1): max_heapify(arr, n, i) ``` 这段程序展示了如何把给定的数据序列构造成最大堆的形式。这有助于理解不同类型的堆是如何工作的以及它们之间细微差别所在。