面试题：C语言堆排序的时间复杂度分析

堆构建的时间复杂度
- 推导过程：
  - 构建堆是从最后一个非叶子节点开始，依次向上调整节点以满足堆的性质。对于一个具有n个元素的完全二叉树，其高度h = ⌊log₂n⌋ + 1。
  - 第i层的节点数最多为2^i个。调整每个节点时，最多需要比较和交换的次数等于该节点到叶子节点的最长路径长度，也就是树的高度减去该节点所在的层数。
  - 假设树高为h，从倒数第二层（第h - 2层）开始调整，该层节点数为2^(h - 2)，每个节点最多调整1次；倒数第三层（第h - 3层）节点数为2^(h - 3)，每个节点最多调整2次，以此类推，直到根节点（第0层）最多调整h - 1次。
  - 总的调整次数S = 2^(h - 2) * 1+2^(h - 3) * 2 +...+ 2^0 * (h - 1)。
  - 根据等比数列求和公式以及n = 2^h - 1（完全二叉树节点数和高度关系），可以得出S < 2n，所以堆构建的时间复杂度为O(n)。
- 代码示例（以大顶堆构建为例）：

void buildMaxHeap(int arr[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }
}

这里n / 2 - 1是最后一个非叶子节点的索引，循环从这个节点开始，对每个节点调用heapify函数（调整节点以满足堆性质的函数），虽然每个heapify操作时间复杂度是O(log n)，但整体构建堆的过程是O(n)。

每次删除堆顶元素并调整堆的时间复杂度
- 推导过程：
  - 删除堆顶元素后，将堆的最后一个元素放到堆顶，然后从堆顶开始向下调整堆以恢复堆的性质。
  - 由于堆是一个完全二叉树，高度h = ⌊log₂n⌋ + 1。每次调整时，最多需要比较和交换的次数等于树的高度，即O(log n)。
- 代码示例（以大顶堆删除堆顶元素并调整为例）：

int extractMax(int arr[], int &n) {
    int root = arr[0];
    arr[0] = arr[n - 1];
    n = n - 1;
    heapify(arr, n, 0);
    return root;
}

这里先保存堆顶元素，将最后一个元素移到堆顶，堆大小减1，然后调用heapify函数从堆顶（索引0）开始调整堆，这个调整过程时间复杂度为O(log n)。

整个排序过程时间复杂度为O(n log n)的原因
- 堆排序过程首先构建堆，时间复杂度为O(n)。
- 然后进行n - 1次删除堆顶元素并调整堆的操作，每次操作时间复杂度为O(log n)。
- 所以总的时间复杂度为O(n)+O((n - 1)log n)，在大O表示法中，忽略常数项和低阶项，O(n)+O((n - 1)log n)=O(n log n)。
- 代码示例（完整堆排序）：

void heapSort(int arr[], int n) {
    buildMaxHeap(arr, n);
    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

先调用buildMaxHeap构建大顶堆，然后通过循环将堆顶元素（最大值）和当前未排序部分的最后一个元素交换，再对前i个元素调用heapify调整堆，这个过程整体时间复杂度为O(n log n)。

星途面试题库

面试题：C语言堆排序的时间复杂度分析

知识考点

面试题答案