#pragma once
#include
#include
#include
#include
typedef int HPDataType;
typedef struct Heap
{
HPDataType* a;//指向用于存放堆数据的数组
int size;//记录有效数据个数
int capacity;//记录容量
}HP;
void HeapInit(HP* php);//初始化函数
void HeapDestroy(HP* php);//销毁函数
void HeapPint(HP* php);//打印
void Swap(HPDataType* x, HPDataType* y);//交换函数
void AdjustUP(HPDataType* a, int child);//向上调整
void Rec_AdjustUP(HPDataType* a, int child);//向上调整(递归版本)
void HeapPush(HP* php, int x);//插入
void AdjustDown(HPDataType* a, int size, int parent);//向下调整
void Rec_AdjustDown(HPDataType* a, int size, int parent);//向下调整(递归版本)
void HeapPop(HP* php);//删除
HPDataType HeapTop(HP* php);//获取堆顶值
bool HeapEmpty(HP* php);//判空
int HeapSize(HP* php);//获取堆的数据个数
Heap.c
#include"Heap.h"
void HeapInit(HP* php)//初始化函数
{
assert(php);
php->a = NULL;
php->size = php->capacity = 0;
}
void HeapDestroy(HP* php)//销毁函数
{
assert(php);
free(php->a);
php->a = NULL;
php->size = php->capacity = 0;
}
void HeapPint(HP* php)//打印
{
for (int i = 0; i < php->size; i++)
{
printf("%d ", php->a[i]);
}
putchar(10);//换行
}
void Swap(HPDataType* x, HPDataType* y)//交换函数
{
HPDataType tmp = *x;
*x = *y;
*y = tmp;
}
void AdjustUP(HPDataType* a, int child)//向上调整(小根堆)(非递归)
{
assert(a);
int parent = (child - 1) / 2;//找到父节点
while (child > 0)//最坏要一直调整到堆顶
{
if (a[child] < a[parent])//如果子节点小于父节点,不满足小根堆的性质,交换
{
Swap(&a[child], &a[parent]);
child = parent;//更新父子节点,准备下一次比较
parent = (child - 1) / 2;
}
else
break;//如果子节点大于父节点,满足小根堆的性质,结束循环
}
}
void HeapPush(HP* php, int x)//插入
{
assert(php);
if (php->size == php->capacity)//插入要考虑扩容问题
{
int newcapacity = php->capacity == 0 ? 4 : php->capacity * 2;
HPDataType* tmp = (HPDataType*)realloc(php->a, newcapacity * sizeof(int));
if (tmp == NULL)//内存不足的情况下,realloc有可能失败,要进行检查
{
printf("realloc fail!\n");
exit(-1);//非正常运行导致退出程序
}
php->a = tmp;
//realloc有可能原地扩容所以不用free原空间
php->capacity = newcapacity;
}
php->a[php->size] = x;//尾插
AdjustUP(php->a, php->size);//向上调整
php->size++;//有效数据个数加一
}
void AdjustDown(HPDataType* a, int size, int parent)//向下调整(小堆)(非递归)
{
assert(a);
int child = parent * 2 + 1;
while (child < size)//最坏情况下,要一直换到叶子节点
{
//找到较小的孩子
if ((child + 1 < size) && (a[child] > a[child + 1]))//如果右孩子比左孩子小
{
child++;
}
//向下调整
if (a[child] < a[parent])//如果子节点小于父节点,不满足小根堆的性质,交换
{
Swap(&a[child], &a[parent]);
parent = child;//更新父子节点,准备下一次比较
child = parent * 2 + 1;
}
else
{
break;//如果子节点大于父节点,满足小根堆的性质,结束循环
}
}
}
void HeapPop(HP* php)//删除(删除堆顶元素)
{
assert(php);
Swap(&php->a[0], &php->a[php->size - 1]);//交换第一个元素(堆顶元素)和最后一个元素
--php->size;//尾删
AdjustDown(php->a, php->size, 0);//向下调整
}
HPDataType HeapTop(HP* php)//获取堆顶值
{
assert(php);
assert(php->size > 0);
return php->a[0];
}
bool HeapEmpty(HP* php)//判空
{
assert(php);
return php->size == 0;
}
int HeapSize(HP* php)//获取堆的数据个数
{
assert(php);
return php->size;
}
void Rec_AdjustUP(HPDataType* a, int child)//向上调整(小根堆)(递归版本)
{
assert(a);
int parent = (child - 1) / 2;//找到父节点
/*if (child == 0)
return;*/
//递归到最后,child == parent
if (a[child] < a[parent])//如果子节点小于父节点,不满足小根堆的性质,交换
{
Swap(&a[child], &a[parent]);
child = parent;//更新父子节点,准备下一次比较
Rec_AdjustUP(a, child);
}
else
{
return;
}
}
void Rec_AdjustDown(HPDataType* a, int size, int parent)//向下调整(小根堆)(递归版本)
{
assert(a);
int child = parent * 2 + 1;
if (child >= size)//最坏情况下,要一直换到叶子节点
return;
//找到较小的孩子
if ((child + 1 < size) && (a[child] > a[child + 1]))//如果右孩子比左孩子小
{
child++;
}
//向下调整
if (a[child] < a[parent])//如果子节点小于父节点,不满足小根堆的性质,交换
{
Swap(&a[child], &a[parent]);
parent = child;//更新父子节点,准备下一次比较
Rec_AdjustDown(a, size, parent);
}
else
{
return;//如果子节点大于父节点,满足小根堆的性质,结束循环
}
}
//void AdjustDown(HP* php)//向下调整(小堆)
//{
// assert(php);
// //assert(php->size > 0);//当数据个数大于零时才能进行删除
//
// int parent = 0;
// int childleft = parent * 2 + 1;
// int childright = parent * 2 + 2;
//
// while (childright < php->size)//交换,直到超出size范围(最多到叶子节点)
// {
// int min = php->a[childleft] > php->a[childleft] ? childleft : childright;//选出更小的孩子
//
// if (php->a[parent] > php->a[min])//如果孩子比父亲小,交换(向下调整)
// {
// HPDataType tmp = php->a[parent];
// php->a[parent] = php->a[min];
// php->a[min] = tmp;
//
// parent = min;//更新父子位置(向下调整一辈)
// childleft = parent * 2 + 1;
// childright = parent * 2 + 2;
// }
// else
// {
// break;//如果最小的孩子都不比父亲小,证明是小堆不需要交换
// }
// }
//
//}
Heaptest.c(测试用例)
#include"Heap.h"
int main()
{
/*HP hp;
HeapInit(&hp);
HeapPush(&hp, 5);
HeapPush(&hp, 4);
HeapPush(&hp, 3);
HeapPush(&hp, 2);
HeapPush(&hp, 1);
HeapPint(&hp);
printf("TOP:%d\n\n", HeapTop(&hp));
HeapPop(&hp);
printf("TOP:%d\n", HeapTop(&hp));
HeapPint(&hp);
printf("Size:%d\n", HeapSize(&hp));
HeapDestroy(&hp);
return 0;*/
/*int a[] = { 2,3,4,5,6,1 };
Rec_AdjustUP(a, 5);*/
int a[] = { 6,1,2,3,4,5 };
Rec_AdjustDown(a, 5, 0);
for (int i = 0; i < 6; i++)
{
printf("%d ", a[i]);
}
putchar(10);
return 0;
}
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)