数据结构：堆、堆排序与 TOP-K 问题详解

前言

本文介绍堆（Heap）数据结构及其在 C 语言中的实现。内容涵盖堆的定义、数组存储规则、向上调整与向下调整算法、建堆方法、堆的插入删除操作，以及基于堆实现的堆排序和 TOP-K 问题解决方案。

什么是堆？

堆（Heap）：是一种特殊的完全二叉树结构。

性质：

1. 堆序性：每个节点的值必须满足与子节点的大小关系。
   • 最大堆（大根堆）：父节点的值 ≥ 子节点的值（根节点最大）。
   • 最小堆（小根堆）：父节点的值 ≤ 子节点的值（根节点最小）。
2. 完全二叉树：除了最后一层，其他层必须填满，且最后一层从左到右填充。

堆的实现方式

堆常见的实现方式主要是基于数组。这是因为堆是完全二叉树，而数组能高效地存储完全二叉树结构。

数组实现的存储规则：把堆中的元素按完全二叉树的层序遍历顺序存放在数组里。 假设根节点在数组中的索引为 0，对于节点 i：

• 左子节点索引为：2 * i + 1
• 右子节点索引为：2 * i + 2
• 父节点索引为：(i - 1) / 2

例如：有一个最小堆 [1, 3, 4, 7, 8, 9]，根节点 1 的索引是 0，其左子节点 3 索引为 1，右子节点 4 索引为 2。

typedef int HPDataType;
typedef struct Heap {
    // 记录数组的容量
    int capacity;
    // 记录当前数组中元素的数量
    int size;
    // 使用数组存储堆中的节点
    HPDataType* a;
} HP;

堆的核心算法

堆的高效性依赖于两个核心算法：向上调整算法（Heapify Up） 和 向下调整算法（Heapify Down）。

向上调整算法

当新元素插入堆的末尾时，通过向上调整使其满足堆序性。

执行流程：

1. 将新元素插入堆的末尾（数组的最后位置）。
2. 比较新元素与其父节点的值：若不满足堆序性（如：在最小堆中，新元素比父节点小），则交换两者。
3. 重复此过程，直到新元素到达合适位置或成为根节点。

时间复杂度：O(log n)，其中 n 为堆的元素数量。

向下调整算法

当堆顶元素被删除或替换时，通过向下调整重新恢复堆序性。

执行流程：

1. 将堆顶元素替换为堆的最后一个元素（或者：删除堆顶元素后，移动最后元素至堆顶）。