核心知识点梳理#

1. 堆的基础定义：堆是一棵完全二叉树，分为大顶堆和小顶堆。大顶堆要求每个父节点的值都大于等于其子节点的值，堆顶元素为全局最大值；小顶堆则要求每个父节点的值小于等于其子节点的值，堆顶元素为全局最小值。408考纲中堆排序默认采用大顶堆实现升序排序。
2. 堆的顺序存储：堆通常采用数组实现完全二叉树的顺序存储，下标为i的节点的左子节点下标为2i+1，右子节点下标为2i+2，父节点下标为(i-1)/2（整数除法），这是堆排序代码实现的核心映射关系。
3. 堆排序的核心流程
   • 建堆：将无序序列构建为大顶堆，建堆的起始位置为最后一个非叶子节点，即下标为n/2 -1的节点，从后向前依次对每个非叶子节点执行向下调整（siftDown）操作，建堆的时间复杂度为$O(n)$。
   • 排序迭代：将堆顶元素与当前堆的最后一个元素交换，将当前堆的规模减1，随后对新的堆顶元素执行向下调整操作，重复该过程直至堆的规模为1，整体堆排序的时间复杂度为$O(n\log n)$。
4. 考研高频考点拓展
   • 堆排序属于选择排序类算法，是原地排序算法，空间复杂度为$O(1)$；
   • 堆排序是不稳定的排序算法，因为交换堆顶和末尾元素的过程可能破坏相同元素的相对位置；
   • 常考题型包括：给定无序序列构造大顶堆、推演堆排序的每一趟排序结果、计算堆排序的时间复杂度、对比堆排序与其他内部排序算法的优劣。