面试题：C++ 堆排序在不同数据场景下的优化

优化思路

利用已有序部分：对于部分有序数组，可以利用其有序性减少堆构建和调整的工作量。例如，已经有序的子数组可以直接保留，不需要参与堆的构建。
增量式堆构建：不是对整个数组进行传统的堆构建，而是从无序部分开始，逐步将元素插入到已构建好的堆结构中。

关键代码片段

#include <iostream>
#include <vector>

// 调整堆的函数
void heapify(std::vector<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 optimizedHeapSort(std::vector<int>& arr) {
    int n = arr.size();

    // 找到无序部分的起始位置
    int sortedEnd = 0;
    while (sortedEnd + 1 < n && arr[sortedEnd] <= arr[sortedEnd + 1]) {
        sortedEnd++;
    }

    // 从无序部分开始构建堆
    for (int i = sortedEnd / 2 - 1; i >= 0; i--) {
        heapify(arr, sortedEnd + 1, i);
    }

    // 逐步将堆顶元素放到数组末尾，并调整堆
    for (int i = sortedEnd; i > 0; i--) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }

    // 合并有序部分和排好序的无序部分
    std::vector<int> result;
    int i = 0, j = sortedEnd + 1;
    while (i <= sortedEnd && j < n) {
        if (arr[i] <= arr[j]) {
            result.push_back(arr[i++]);
        } else {
            result.push_back(arr[j++]);
        }
    }
    while (i <= sortedEnd) {
        result.push_back(arr[i++]);
    }
    while (j < n) {
        result.push_back(arr[j++]);
    }
    arr = result;
}

空间复杂度变化分析

优化前：传统堆排序的空间复杂度为 $O(1)$，因为只需要常数级别的额外空间用于交换元素。
优化后：在关键代码中，虽然增加了合并有序部分的操作，但额外使用的空间为 $O(n)$，因为创建了一个临时的 result 向量来存储合并结果。然而，如果不使用临时向量，而是采用原地合并算法（例如归并排序的原地合并思想），空间复杂度可以优化回 $O(1)$。总的来说，优化后如果不采用原地合并，空间复杂度变为 $O(n)$，若采用原地合并则仍保持为 $O(1)$。

星途面试题库

面试题：C++ 堆排序在不同数据场景下的优化

知识考点

面试题答案

优化思路

关键代码片段

空间复杂度变化分析