1. 堆的概念和定义
1.1 堆
堆本质上是一种特殊的完全二叉树。根据根节点的大小关系，通常分为大根堆和小根堆。
- 大根堆（大顶堆）：任意父节点的值都不小于其子节点的值，根节点最大。
- 小根堆（小顶堆）：任意父节点的值都不大于其子节点的值，根节点最小。
关键性质在于：堆中某个结点的值总是不大于或不小于其父结点的值，且堆总是一棵完全二叉树。这意味着我们可以用数组来紧凑地存储堆结构，无需额外的指针开销。
1.2 二叉树的性质
对于有 n 个结点的二叉树，如果从上到下、从左到右从 0 开始依次编号，对于编号为 i 的结点有以下下标计算规律：
- 父结点：
(i - 1) / 2 - 左孩子结点：
2 * i + 1 - 右孩子结点：
2 * i + 2
若 2 * i + 1 或 2 * i + 2 大于等于 n，则说明该结点没有对应的左右孩子。
2. 堆的实现
在 C 语言中，我们通常使用动态数组配合结构体来封装堆的操作接口。以下是堆的基本结构定义及常用函数声明。
typedef int HPDataType;
typedef struct Heap {
HPDataType* a; // 底层数组
int size; // 当前元素个数
int capacity; // 当前容量
} HP;
// 默认初始化堆
void HPInit(HP* php);
// 利用给定数组初始化堆
void HPInitArray(HP* php, HPDataType* a, int n);
// 堆的销毁
void HPDestroy(HP* php);
// 堆的插入
void HPPush(HP* php, HPDataType x);
// 获取堆顶数据
HPDataType HPTop(HP* php);
// 删除堆顶的数据
void ;
;
;
;
;
