一、堆的概念
堆是一种顺序存储完全二叉树的数据结构。
二、堆的一些性质
堆分为小堆和大堆：
小堆要求父亲结点数据小于孩子结点；
大堆要求父亲结点数据小于孩子结点。
如何根据孩子结点下标找到父亲结点？
parent = (child - 1) / 2
如何根据父亲结点下标找到孩子结点？
child = 2 * parent 1 （左孩子）
三、堆的结构定义
堆的结构中包含数组、堆大小、堆容量
//堆的结构定义
typedef int HPDataType;
typedef struct Heap {
HPDataType* a;
int size;
int capacity;
}HP;
四、堆的初始化
将数组初始化为空，堆大小和容量都初始化为0
//堆的初始化
void HPInit(HP* php)
{
php->a = NULL;
php->size = 0;
php->capacity = 0;
}
五、堆打印
打印数组
//堆打印
void HPPrint(HP* php)
{
assert(php);
for (int i = 0; i < php->size; i )
{
printf("%d ", php->a[i]);
}
printf("n");
}
六、向上调整算法
孩子结点与父亲结点比较，如果孩子结点小于父亲结点，就将孩子结点与父亲结点交换。
注意第二个循环条件：是 child > 0，为什么不是 parent >=0 呢？
因为parent最小是0，永远不会小于0。但是该代码也能跑，因为当parent为0时，重置下标时，child重置为0，而parent = (child - 1) / 2也重置为0，此时a[child] = a[parent]，因此循环结束。
//向上调整算法
void AdjustUp(HPDataType*a, int child)
{
int parent = (child - 1) / 2;
while (a[child] < a[parent] && child > 0)//孩子结点比父亲结点小
{
//交换父亲结点和孩子结点的数据
HPDataType tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
//父亲结点和孩子结点下标重置
child = parent;
parent = (child - 1) / 2;
}
}
七、堆的插入
插入数据前先检查堆容量是否足够，容量不够则扩容，容量足够则将数据存入数组中，再用向上调整算法将新插入的数据进行调整。
//堆的插入
void HPPush(HP* php, HPDataType x)
{
assert(php);
//堆扩容
if (php->size ==php->capacity )
{
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);
}
php->a = tmp;
php->capacity = newcapacity;
}
php->a[php->size ] = x;
//向上调整算法
AdjustUp(php->a, php->size - 1);
}
八、向下调整算法
将父亲结点与孩子结点比较，如果父亲结点大于孩子结点，则交换
由于可能有两个孩子结点，先要确认右孩子是否存在，如果存在取较小的孩子结点与父亲结点交换
//向下调整算法
void AdjustDown(HPDataType* a, int size, int parent)
{
int child = parent * 2 1;
while (child < size)
{
if (child 1 < size)//存在右孩子
{
if (a[child 1] < a[child])//右孩子比左孩子小，用右孩子顶替父亲结点位置
{
child = child 1;
}
}
if (a[child] < a[parent])
{
//交换父亲结点与孩子结点
HPDataType tmp = a[child];
a[child] = a[parent];
a[parent] = tmp;
//重置父亲结点和孩子结点
parent = child;
child = parent * 2 1;
}
else
{
break;
}
}
}
九、堆的删除
堆的删除是删除堆顶元素，因为删除堆尾元素是没有意义的。
删除堆顶即删除二叉树的根，删除后还要使之成为一个完全二叉树，所以需要用次小值去顶替堆顶的位置。
具体方法：
先将堆尾元素与堆顶元素交换位置，然后删除堆尾元素，再利用向下调整算法将堆顶位置元素向下调整到合适的位置。
//堆的删除
void HPPop(HP* php)
{
assert(php);
assert(php->size);//空堆不可删除
//交换堆顶元素和堆底元素
HPDataType tmp = php->a[0];
php->a[0] = php->a[php->size - 1];
php->a[php->size - 1] = tmp;
//删除堆底元素
php->size--;
//向下调整算法
AdjustDown(php->a, php->size, 0);
}
十、取堆顶元素
先判断堆是否为空，不空则返回堆顶元素
//取堆顶元素
HPDataType HPTop(HP* php)
{
assert(php);
assert(php->size);
return php->a[0];
}
十一、求堆大小
返回size即可
//求堆大小
size_t HPSize(HP* php)
{
assert(php);
return php->size;
}
十二、堆判空
利用size判断堆是否为空
//判空
bool HPEmpty(HP* php)
{
assert(php);
return php->size == 0;
}
十三、测试代码
void test01()
{
//创建堆
HP hp;
//初始化堆
HPInit(&hp);
//堆插入
HPPush(&hp, 1);
HPPush(&hp, 5);
HPPush(&hp, 3);
HPPush(&hp, 6);
HPPush(&hp, 7);
HPPush(&hp, 5);
HPPush(&hp, 4);
HPPush(&hp, 9);
HPPush(&hp, 8);
//堆打印
HPPrint(&hp);
//堆插入
HPPush(&hp, 1);
//堆打印
HPPrint(&hp);
//堆删除
HPPop(&hp);
//堆打印
HPPrint(&hp);
//取堆顶元素
printf("%dn", HPTop(&hp));
//求堆大小
printf("%zdn", HPSize(&hp));
//堆判空
if (HPEmpty(&hp))
printf("空n");
else
printf("非空n");
}
int main()
{
test01();
return 0;
}
