⼆叉树性质（左右孩子位置）

实现堆的顺序结构

堆的结构体

typedef int HPDataType;  // 堆中存储的数据类型
typedef struct Heap {HPDataType* arr;    // 存储堆元素的数组int size;           // 当前堆中元素的数量int capacity;       // 堆的容量
} HP;

核心函数功能

• HPInit：初始化堆，将数组指针置空，大小和容量设为 0
• HPDestroy：销毁堆，释放动态分配的内存
• HPPrint：打印堆中的所有元素
• Swap：交换两个整数的值
• AdjustUp：向上调整算法，用于插入元素后维持堆的性质
• HPPush：向堆中插入元素
• HPEmpty：判断堆是否为空
• AdjustDown：向下调整算法，用于删除元素后维持堆的性质
• HPPop：删除堆顶元素
• HPTop：获取堆顶元素的值

void HPInit(HP* php);
void HPDestroy(HP* php);
void HPPrint(HP* php);void Swap(int* x, int* y);
void AdjustUp(HPDataType* arr, int child);
void AdjustDown(HPDataType* arr, int parent, int n);void HPPush(HP* php, HPDataType x);
void HPPop(HP* php);
//取堆顶数据
HPDataType HPTop(HP* php);// 判空
bool HPEmpty(HP* php);

初始化

void HPInit(HP* php)
{php->arr = NULL;php->size = php->capacity = 0;
}

打印

void HPPrint(HP* php)
{for (int i = 0; i < php->size; i++){printf("%d ", php->arr[i]);}printf("\n");
}

交换数据

void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}

如果不用指针，直接传递变量的值，函数内部的交换操作不会影响到函数外部的变量

向上调整法

void AdjustUp(HPDataType* arr, int child)
{int parent = (child - 1) / 2;while (child > 0){//大堆：>//小堆：<if (arr[child] > arr[parent]){//调整Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else {break;}}
}

当新元素被插入到堆的末尾时，可能会破坏堆的性质（父节点值大于子节点值）。AdjustUp 函数通过将新插入的元素（从最后一个位置）向上移动，与父节点比较并交换，直到重新满足堆的性质。

细节：

1. 父节点索引计算公式 (child - 1) / 2 是由完全二叉树的性质决定的

2. 循环终止条件 child > 0 确保不会越界访问（根节点没有父节点）

3. 若要实现小根堆，只需将比较运算符 > 改为 <

入堆

//入堆
void HPPush(HP* php, HPDataType x)
{assert(php);//判断空间是否足够if (php->size == php->capacity){int newCapacity = php->capacity == 0 ? 4 : 2 * php->capacity;HPDataType* tmp = (HPDataType*)realloc(php->arr, newCapacity * sizeof(HPDataType));if (tmp == NULL){perror("realloc fail!");exit(1);}php->arr = tmp;php->capacity = newCapacity;}php->arr[php->size] = x;//向上调整AdjustUp(php->arr, php->size);++php->size;
}

• 新元素先放在数组末尾（对应完全二叉树的最后一个位置）
• 调用AdjustUp函数向上调整，确保插入后仍满足堆的性质
• 最后更新堆的元素数量

注意：

realloc 的核心作用是重新分配已有的动态内存块，可以：

• 当原内存块后面有足够空间时，直接在原地扩展，无需复制数据
• 当空间不足时，自动分配新内存块并将原数据复制过去
  而 malloc 只能分配全新的内存块，如果用 malloc 实现扩容，需要手动完成
• 当堆的内存块后面有连续的空闲空间时，realloc 可以直接扩展内存，避免数据复制，效率远高于 malloc + memcpy + free 的组合。

时间复杂度

• 扩容操作的时间复杂度：O (n)（最坏情况，需要复制所有元素），但由于采用 2 倍扩容策略，平均下来是 O (1)
• 向上调整操作的时间复杂度：O (log n)（最多需要调整到根节点，路径长度为堆的高度）
• 因此，HPPush操作的平均时间复杂度为 O (log n)。

判空

// 判空
bool HPEmpty(HP* php)
{assert(php);return php->size == 0;
}

向下调整法

//向下调整算法
void AdjustDown(HPDataType* arr, int parent, int n)
{int child = parent * 2 + 1;//左孩子while (child < n){//大堆：<//小堆：>if (child + 1 < n && arr[child] < arr[child + 1]){child++;}//大堆: >//小堆：<if (arr[child] > arr[parent]){//调整Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else {break;}}
}

• HPDataType* arr：存储堆元素的数组
• int parent：需要向下调整的起始父节点索引（通常是堆顶元素索引 0）
• int n：堆中有效元素的个数（调整范围不超过此值）

• 关键细节：

  • 先判断右孩子是否存在且更大（child + 1 < n确保不越界），目的是找到两个孩子中的最大值
  • 若子节点大于父节点，交换后继续向下调整；否则说明已满足堆性质，停止调整
  • 若要实现小根堆，只需将两处比较运算符<和>分别改为>和<

带入实例：

假设大根堆当前状态为 [60, 50, 40, 30]，删除堆顶元素后，最后一个元素30移到堆顶，数组变为 [30, 50, 40, ...]（size减 1 后n=3）：

时间复杂度

AdjustDown的时间复杂度为O(log n)，因为最多需要调整到堆的最底层，路径长度为堆的高度（完全二叉树的高度为log2(n+1)）。

1. parent=0，child=1（左孩子 50）
2. 右孩子child+1=2（值 40）存在，50>40，所以child保持 1
3. 子节点 50 > 父节点 30，交换后数组为 [50, 30, 40]，parent=1，child=3
4. child=3不小于n=3，循环终止，调整完成，结果为 [50, 30, 40]，满足大根堆性质

删除堆顶元素：

void HPPop(HP* php)
{assert(!HPEmpty(php));// 0 php->size-1Swap(&php->arr[0], &php->arr[php->size - 1]);--php->size;//向下调整AdjustDown(php->arr, 0, php->size);
}

• 时间复杂度：O (log n)，主要由AdjustDown操作决定
• 空间复杂度：O (1)，仅使用常数级额外空间

获取堆顶元素

//取堆顶数据
HPDataType HPTop(HP* php)
{assert(!HPEmpty(php));return php->arr[0];
}

堆的销毁

void HPDestroy(HP* php)
{if (php->arr)free(php->arr);php->arr = NULL;php->size = php->capacity = 0;
}

测试代码（堆排序---向下调整法建堆）

void arrPrint(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}
void BubbleSort(int* arr, int n)
{for (int i = 0; i < n; i++){for (int j = 0; j < n - i - 1; j++){if (arr[j] > arr[j + 1]){Swap(&arr[j], &arr[j + 1]);}}}
}//堆排序
void HeapSort1(int* arr, int n)
{HP hp; //——————借助数据结构堆来实现堆排序HPInit(&hp);for (int i = 0; i < n; i++){HPPush(&hp, arr[i]);}int i = 0;while (!HPEmpty(&hp)){int top = HPTop(&hp);arr[i++] = top;HPPop(&hp);}HPDestroy(&hp);
}void HeapSort(int* arr, int n)
{//建堆——向下调整算法建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, i, n);}//堆排序int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDown(arr, 0, end);end--;}}void test01()
{HP hp;HPInit(&hp);HPPush(&hp, 56);HPPush(&hp, 10);HPPush(&hp, 15);HPPush(&hp, 30);//HPPush(&hp, 70);//HPPush(&hp, 25);HPPrint(&hp);HPPop(&hp);HPPrint(&hp);HPPop(&hp);HPPrint(&hp);HPPop(&hp);HPPrint(&hp);HPPop(&hp);HPPrint(&hp);HPDestroy(&hp);
}void test02()
{HP hp;HPInit(&hp);HPPush(&hp, 56);HPPush(&hp, 10);HPPush(&hp, 15);HPPush(&hp, 30);HPPrint(&hp);while (!HPEmpty(&hp)){int top = HPTop(&hp);printf("%d ", top);HPPop(&hp);}HPDestroy(&hp);
}int main()
{//test01();//test02();int arr[6] = { 19,15,20,17,13,10 };printf("排序之前：");arrPrint(arr, 6);//堆排序HeapSort(arr, 6);printf("排序之后：");arrPrint(arr, 6);return 0;
}