当前位置：首页 > news >正文

吊打面试官：手撕堆排序与 Top-K 问题的最优解

news 2026/5/12 17:46:59

1. 堆的概念与逻辑结构

堆在逻辑上是一棵完全二叉树，但在物理存储上通常使用顺序表（数组）。

大根堆（Max Heap）：根节点的值大于或等于其左右孩子节点的值。
小根堆（Min Heap）：根节点的值小于或等于其左右孩子节点的值。

数组下标的规律

对于下标为i的节点：

父节点下标：(i - 1) / 2
左孩子下标：2 * i + 1
右孩子下标：2 * i + 2

2. 核心算法：向下调整与向上调整

向上调整 (AdjustUp)

主要用于插入元素。当新数据插入到数组末尾时，通过不断与父节点比较并交换，使其“浮”到正确位置。

时间复杂度：O(log n)

向下调整 (AdjustDown)

主要用于删除堆顶元素或建堆。将根节点与其较小的孩子交换，使其“沉”到正确位置。

前提条件：左右子树必须已经是堆。
时间复杂度：O(log n)

3. 建堆的时间复杂度解析（重点）

向上调整建堆：相当于不断插入元素，复杂度为O(n log n)。
向下调整建堆：从最后一个非叶子节点开始。由于底层节点多但调整路径短，高层节点少但路径长，经数学推导（错位相减法），总复杂度为O(n)。

4. C 语言代码实现

#include <stdio.h> #include <stdlib.h> #include <stdbool.h> // 交换函数 void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } // 向下调整（小根堆） void AdjustDown(int* a, int n, int parent) { int child = parent * 2 + 1; // 假设左孩子最小 while (child < n) { // 找出左右孩子中较小的一个 if (child + 1 < n && a[child + 1] < a[child]) { child++; } // 如果孩子比父亲小，交换 if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } else { break; } } } // 向上调整（小根堆） void AdjustUp(int* a, int child) { int parent = (child - 1) / 2; while (child > 0) { if (a[child] < a[parent]) { Swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } } void CreatHeap(int* a, int n) { // 1. 建大堆 // 这里以向下调整建堆为例 O(n) for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } } int main() { int arr[] = {15, 18, 28, 34, 65, 19, 49, 25, 37, 27}; int n = sizeof(arr) / sizeof(arr[0]); printf("原始数组: "); for(int i=0; i<n; i++) printf("%d ", arr[i]); CreatHeap(arr, n); printf("\n建堆后: "); for(int i=0; i<n; i++) printf("%d ", arr[i]); return 0; }

1.方案 A：向下调整建堆（最优解）

代码：从最后一个非叶子节点开始，往根部走。

for (int i = (n - 2) / 2; i >= 0; i--) { AdjustDown(a, n, i); }

原理：先保证子树是堆，再合并成大子树。
效率：O(n)。

2.方案 B：向上调整建堆（次优解）

代码：从第 2 个元素开始，往尾部走。
```
for (int i = 1; i < n; i++) { AdjustUp(a, i); }
```
原理：模拟不断插入新元素的过程。每进来一个数，都让它向上浮动到合适位置。
效率：O(n log n)。

深度解析：为什么 O(n)比 O(n log n)快？

向下调整建堆（O(n)）聪明的点在于：

底层节点多：在完全二叉树中，约 50\% 的节点都在最后一层。
移动步数少：向下调整时，底层的节点只需要移动 0 或 1 步；只有顶层的少量节点需要移动 log n 步。
总结：多对少（节点多的走得少），所以总和是 O(n)。

向上调整建堆（O(n log n)）的问题在于：

底层节点多：最后一层节点占了一半。
移动步数多：每个底层节点向上调整时，最多都要走 log n步才能到根部。
总结：多对多（节点多的走得多），所以总和是 O(n log n)。

5. 进阶应用一：堆排序 (Heap Sort)

堆排序是一种利用堆结构设计的选择排序。其核心思想是：利用堆顶始终是最大（或最小）值的特性，不断提取堆顶。

关键点：升序建大堆，降序建小堆

很多人容易记反。逻辑如下（以升序为例）：

建大堆：堆顶是当前最大的数。
交换与调整：将堆顶（最大值）与数组末尾元素交换。此时最大值已归位。
缩小范围：将数组有效长度减 1，对新的堆顶进行向下调整，使其重新成为大堆。
循环：重复上述过程直到只剩一个元素。

代码片段 (升序)

void HeapSort(int* a, int n) { // 1. 从最后一个非叶子节点开始，向下调整建大堆 (O(n)) for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); // 注意：此处 AdjustDown 内部需实现大堆逻辑 } // 2. 交换堆顶和堆末尾，不断调整 (O(nlogn)) int end = n - 1; while (end > 0) { Swap(&a[0], &a[end]); AdjustDown(a, end, 0); // 调整剩余的 end 个元素 end--; } }

6. 进阶应用二：Top-K 问题

场景描述：从 100亿个数据中，找出最大的前 100 个数。

内存限制：数据量太大，无法一次性加载到内存排序。

最优解法：利用堆

如果我们求前 K 个最大的数，步骤如下：

取前 K 个数建立一个小堆。
遍历剩余数据：将剩余的每个数据与堆顶元素（堆中最小的那个）比较。
替换与调整：如果该数大于堆顶，则替换堆顶，并进行一次向下调整。
结果：遍历完成后，堆里的 K 个元素就是最大的前K 个。

为什么用小堆？> 因为小堆的堆顶是“守门员”。只要你比堆中最小的（堆顶）还要大，你就够格进堆。进堆后向下调整，新的“守门员”会浮现。

C 语言代码实现 (Top-K)

void PrintTopK(int* a, int n, int k) { // 1. 建立一个大小为 k 的小堆 int* minHeap = (int*)malloc(sizeof(int) * k); for (int i = 0; i < k; i++) { minHeap[i] = a[i]; } // 2. 建堆 for (int i = (k - 2) / 2; i >= 0; i--) { AdjustDown(minHeap, k, i); // 小堆调整逻辑 } // 3. 遍历剩余数据，与堆顶比较 for (int i = k; i < n; i++) { if (a[i] > minHeap[0]) { minHeap[0] = a[i]; // 替换堆顶 AdjustDown(minHeap, k, 0); // 重新调整为小堆 } } // 4. 打印结果 for (int i = 0; i < k; i++) { printf("%d ", minHeap[i]); } free(minHeap); }