堆的顺序存储结构实现与核心操作解析
一、树的基本概念与表示方式
树是一种典型的非线性数据结构，由若干个节点构成，具有明确的层级关系。其根节点位于最上层，其余节点可划分为多个互不相交的子树。
- 结点度：指一个节点所拥有的子节点数量。
- 叶节点：度为0的节点，即无子节点。
- 分支节点：除根和叶外的所有节点。
- 父子关系：若节点A有子节点B，则称A为父节点，B为子节点。
- 兄弟节点：共享同一父节点的节点互为兄弟。
- 树的高度：从根到最深叶节点的路径长度。
- 森林：多棵互不相交的树的集合。
在实际存储中，常用"孩子-兄弟"表示法或"双亲"表示法（通过数组记录父节点索引）来构建树结构。
二、二叉树及其特殊形态
二叉树是每个节点最多有两个子节点的树形结构，且左右子树有明确顺序，因此是有序结构。
- 满二叉树：每一层节点数均达到最大值，若高度为h，总节点数为
2^h - 1。 - 完全二叉树：深度为k的有n个节点的二叉树，按层序编号后，与同深度的满二叉树对应位置一致。
三、堆的顺序存储实现原理
由于完全二叉树具有良好的下标规律，可用数组连续存储，实现高效访问：
- 左子节点索引：
parent * 2 + 1 - 右子节点索引：
parent * 2 + 2 - 父节点索引：
(child - 1) / 2
基于此特性，堆可以以数组形式高效实现，分为大根堆（父节点 ≥ 子节点）与小根堆（父节点 ≤ 子节点）。
四、核心调整算法详解
4.1 向上调整（Insert）
当新元素插入末尾后，从该位置开始向上比较并交换，直到满足堆性质。
void AdjustUp(HPDataType* arr, int idx) {
while (idx > 0) {
int parent = (idx - 1) / 2;
if (arr[parent] > arr[idx]) {
Swap(&arr[parent], &arr[idx]);
idx = parent;
} else break;
}
}
4.2 向下调整（Delete Root）
删除堆顶后，将最后一个元素移至根部，再从根向下调整，确保堆结构完整。
void AdjustDown(HPDataType* arr, int root, int size) {
int child = root * 2 + 1;
while (child < size) {
if (child + 1 < size && arr[child] > arr[child + 1])
child++;
if (arr[child] < arr[root]) {
Swap(&arr[root], &arr[child]);
root = child;
child = root * 2 + 1;
} else break;
}
}
五、完整堆结构实现
封装成结构体，支持初始化、插入、删除、取顶、判空等操作，并自动扩容。
头文件（Heap.h）
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int HPDataType;
typedef struct Heap {
HPDataType* data;
int size;
int capacity;
} Heap;
void HeapInit(Heap* hp);
void HeapInitFromArr(Heap* hp, HPDataType* arr, int n);
void HeapDestroy(Heap* hp);
void HeapPrint(Heap* hp);
void HeapPush(Heap* hp, HPDataType val);
void HeapPop(Heap* hp);
HPDataType HeapTop(Heap* hp);
bool HeapIsEmpty(Heap* hp);
源文件（Heap.c）
#define _CRT_SECURE_NO_WARNINGS 1
#include "Heap.h"
void HeapInit(Heap* hp) {
hp->data = NULL;
hp->size = hp->capacity = 0;
}
void HeapInitFromArr(Heap* hp, HPDataType* arr, int n) {
hp->data = (HPDataType*)malloc(n * sizeof(HPDataType));
assert(hp->data);
memcpy(hp->data, arr, n * sizeof(HPDataType));
hp->size = n;
hp->capacity = n;
// 自底向上建堆
for (int i = 1; i < n; ++i)
AdjustUp(hp->data, i);
}
void HeapDestroy(Heap* hp) {
free(hp->data);
hp->data = NULL;
hp->size = hp->capacity = 0;
}
void HeapPrint(Heap* hp) {
for (int i = 0; i < hp->size; ++i)
printf("%d ", hp->data[i]);
printf("\n");
}
void Swap(HPDataType* a, HPDataType* b) {
HPDataType tmp = *a;
*a = *b;
*b = tmp;
}
void AdjustUp(HPDataType* arr, int idx) {
while (idx > 0) {
int parent = (idx - 1) / 2;
if (arr[parent] > arr[idx]) {
Swap(&arr[parent], &arr[idx]);
idx = parent;
} else break;
}
}
void AdjustDown(HPDataType* arr, int root, int size) {
int child = root * 2 + 1;
while (child < size) {
if (child + 1 < size && arr[child] > arr[child + 1])
child++;
if (arr[child] < arr[root]) {
Swap(&arr[root], &arr[child]);
root = child;
child = root * 2 + 1;
} else break;
}
}
void HeapPush(Heap* hp, HPDataType val) {
if (hp->size == hp->capacity) {
int new_cap = hp->capacity ? hp->capacity * 2 : 4;
HPDataType* tmp = (HPDataType*)realloc(hp->data, new_cap * sizeof(HPDataType));
assert(tmp);
hp->data = tmp;
hp->capacity = new_cap;
}
hp->data[hp->size++] = val;
AdjustUp(hp->data, hp->size - 1);
}
void HeapPop(Heap* hp) {
Swap(&hp->data[0], &hp->data[hp->size - 1]);
--hp->size;
AdjustDown(hp->data, 0, hp->size);
}
HPDataType HeapTop(Heap* hp) {
return hp->data[0];
}
bool HeapIsEmpty(Heap* hp) {
return hp->size == 0;
}
