面试题：C++ 堆排序中堆的构建过程

Question

请用C++ 代码实现堆排序中堆的构建部分，假设已有数组int arr[] 及数组长度n，要求清晰注释每一步操作，并说明堆构建的时间复杂度。

Answer 1

// 堆调整函数，将以i为根的子树调整为大顶堆
void heapify(int arr[], int n, int i) {
    int largest = i; // 初始化最大元素为根节点
    int left = 2 * i + 1; // 左子节点索引
    int right = 2 * i + 2; // 右子节点索引

    // 如果左子节点比根节点大
    if (left < n && arr[left] > arr[largest])
        largest = left;

    // 如果右子节点比最大元素大
    if (right < n && arr[right] > arr[largest])
        largest = right;

    // 如果最大元素不是根节点
    if (largest != i) {
        std::swap(arr[i], arr[largest]);

        // 递归调整受影响的子树
        heapify(arr, n, largest);
    }
}

// 构建堆的函数
void buildHeap(int arr[], int n) {
    // 从最后一个非叶子节点开始，自下而上进行堆调整
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
}

堆构建的时间复杂度：构建堆的时间复杂度为 $O(n)$。因为在 buildHeap 函数中，我们从最后一个非叶子节点开始调用 heapify 函数，每次 heapify 操作的时间复杂度为 $O(\log n)$，但由于大部分节点深度较小，综合计算可得构建堆的时间复杂度为线性时间 $O(n)$。