数据结构：堆与链式二叉树详解

1. 堆的概念和定义

1.1 堆

定义：是特殊的二叉树，分为大堆和小堆。

• 大堆（大根堆）：根节点最大的堆。堆中某个结点的值总是不小于其父结点的值。
• 小堆（小根堆）：根节点最小的堆。堆中某个结点的值总是不大于其父结点的值。
• 堆总是一棵完全二叉树。

1.2 二叉树的性质

有 n 个结点的二叉树，从上到下从左到右从 0 开始依次编号，对于编号为 i 的结点有以下性质：

• i 结点的父结点：(i-1)/2
• i 结点的左孩子结点：2i+1
• i 结点的右孩子结点：2i+2
• 若 2i+1 或 2i+2 >= n，则没有左右孩子。

2. 堆的实现

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 HPPop(HP* php);
// 判空
;

;

;

;