如何构建一个堆？

推荐答案

// www.javascriptcn.com code example
def build_heap(arr):
    n = len(arr)
    # 从最后一个非叶子节点开始，向上调整
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)

def heapify(arr, n, i):
    largest = i  # 初始化最大值为当前节点
    left = 2 * i + 1  # 左子节点
    right = 2 * i + 2  # 右子节点

    # 如果左子节点存在且大于当前最大值
    if left < n and arr[left] > arr[largest]:
        largest = left

    # 如果右子节点存在且大于当前最大值
    if right < n and arr[right] > arr[largest]:
        largest = right

    # 如果最大值不是当前节点，交换并继续调整
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

本题详细解读

1. 堆的基本概念

堆是一种特殊的完全二叉树，通常分为最大堆和最小堆。在最大堆中，每个节点的值都大于或等于其子节点的值；在最小堆中，每个节点的值都小于或等于其子节点的值。

2. 构建堆的步骤

构建堆的过程通常称为“堆化”（Heapify）。堆化的目的是将一个无序的数组调整为一个堆结构。具体步骤如下：

1. 从最后一个非叶子节点开始：在完全二叉树中，最后一个非叶子节点的索引为 n//2 - 1，其中 n 是数组的长度。
2. 向上调整：从最后一个非叶子节点开始，依次向上调整每个节点，确保每个节点都满足堆的性质。
3. 递归调整：在调整过程中，如果某个节点的值被交换，需要递归地调整其子节点，以确保整个子树都满足堆的性质。

3. 代码解析

• build_heap(arr)：这个函数用于构建堆。它从最后一个非叶子节点开始，依次调用 heapify 函数来调整每个节点。
• heapify(arr, n, i)：这个函数用于调整以 i 为根节点的子树，使其满足堆的性质。它首先找到当前节点、左子节点和右子节点中的最大值，如果最大值不是当前节点，则交换并递归调整。

4. 时间复杂度

• 构建堆的时间复杂度：构建堆的时间复杂度为 O(n)，其中 n 是数组的长度。这是因为堆化的过程并不是简单的 O(n log n)，而是通过从下到上的调整，使得整体时间复杂度降低到 O(n)。

5. 应用场景

堆结构常用于优先队列、堆排序等场景。通过构建堆，可以高效地获取最大值或最小值，并且在插入和删除操作时保持堆的性质。