简述堆排序的原理，堆适合解决哪类考题?

核心考点

堆的定义与调整、堆排序两阶段、复杂度分析及堆的典型应用场景，重点掌握“建初堆”和“反复取堆顶并调整”。

参考答案(答题要点)

1.堆排序原理：堆排序是一种基于堆的选择排序。以大根堆为例，先将待排序列建成大根堆，此时堆顶为最大元素;再将堆顶与当前无序区末尾元素交换，最大元素归位;然后对剩余无序区重新调整为堆，重复“取堆顶、交换、调整”，直到全部有序。

2.两个阶段：第一阶段建初堆，从最后一个非叶结点开始自底向上向下调整，时间复杂度O(n);第二阶段反复删除堆顶并调整，共n-1次，每次调整O(logn)，总时间复杂度O(nlogn)。

3.复杂度与性质：堆排序最好、最坏、平均时间复杂度均为O(nlogn)，空间复杂度O(1)，属于不稳定排序。升序排序通常用大根堆，降序排序通常用小根堆。

4.堆适合的考题：求前K大或前K小、第K大或第K小元素、动态维护最值、优先队列、任务调度、合并多个有序序列、动态中位数(大根堆与小根堆配合)等。考研中常考判断某序列是否为堆、建堆与调整过程、堆排序每趟结果、复杂度及Top K问题。

5.总结：堆的核心是“完全二叉树顺序存储+局部调整”。看到“动态最值、Top K、第K大/小、优先队列”优先想到堆;看到堆排序过程题，要按建堆、交换、调整一步步写。

易错提醒

建初堆不是从根开始，而是从最后一个非叶结点开始向前调整。升序排序用大根堆，不要与小根堆混淆。每次交换后只调整剩余无序区，已归位元素不再参与调整。堆排序不稳定，且不适用于需要稳定排序的场景。

今日小测

对序列进行升序堆排序时，应建大根堆还是小根堆?为什么?

答案：应建大根堆。因为大根堆堆顶是当前最大值，每次与末尾交换后最大值归位到序列末尾，最终得到升序序列。