【初探数据结构】堆的应用实例（堆排序与TopK问题）

一、引言

堆是一种高效处理优先级问题的数据结构，尤其在动态数据流和排序场景中表现优异。本文将通过堆排序和TopK问题两个经典案例，深入解析堆的实际应用，并提供清晰的代码实现与原理分析。

二、堆排序：将无序数组变为有序序列
1. 堆排序的核心思想
  • 利用最大堆的性质：堆顶元素始终为最大值。
  • 两步走策略：
    1. 建堆
    • 升序 ：建大堆
    • 降序：建小堆
    1. 利用堆删除思想来进行排序
    • 逐次提取堆顶：将堆顶元素（最大值）与数组末尾交换，缩小堆范围，重新调整堆。
2. 详细步骤图解（以升序排序为例）

初始数组：[4, 10, 3, 5, 1]

  1. 构建最大堆：
    • 从最后一个非叶子节点（索引5//2 -1 =1）开始调整。
    • 调整后得到最大堆：[10, 5, 3, 4, 1]。