这篇文章主要为大家介绍了C语言数据结构堆的基本操作实现示例，有需要的朋友可以借鉴参考下，希望能够有所帮助，祝大家多多进步，早日升职加薪
1.基本函数实现
a.代码1(向下调整)
void AdjustDown(DateType*a, int n, int parent) { int child = parent * 2 + 1; while (child a[child + 1]) { ++child; } if (a[parent] > a[child]) { Swap(&a[parent], &a[child]); parent = child; child = parent * 2 + 1; } else { break; } } } 注意:if里面的条件语句(child +1)
b.代码2(向上调整)
void AdjustUp(DateType*a , int child) { int parent = (child - 1) / 2; while (child > 0) { if (a[child] 注意:while里面的条件语句是不能够写成(parent<0)，因为当child==0时，parent=(child - 1) / 2,parent==0,再次进入循环不满足a[child] 把堆顶的数据与最后一个数据交换，再次调整size-1个数据。 a.代码1 运行结果 堆的基本操作今天就分享在到这里了，谢谢你的浏览，如果对你有帮助的话请大家以后多多支持0133技术站！c.代码3(交换）
void Swap(DateType*p1, DateType*p2) { DateType tmp = *p1; *p1 = *p2; *p2 = tmp; }2.建堆
void CreatHeap(Heap*p,DateType*num,int n) { assert(p); p->a = (DateType*)malloc(n * sizeof(DateType)); if (p->a == NULL) { printf("malloc failed\n"); exit(-1); } memcpy(p->a, num, n * sizeof(DateType)); p->size = n; p->capacity = n; //建小堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(p->a, p->size, i); } }3.插入数据
void HeapPush(Heap*p, DateType x) { assert(p); if (p->size == p->capacity) { DateType*tmp = (DateType*)realloc(p->a, (p->capacity) * 2 * sizeof(DateType)); if (tmp == NULL) { printf("realloc failed\n "); exit(-1); } } (p->capacity) *= 2; p->a[p->size] = x; ++(p->size); //向上调整 AdjustUp(p->a, p->size-1); }4. 删除数据
void HeapPop(Heap*p, DateType x) { assert(p); Swap(&p->a[0], &p->a[p->size-1]); --(p->size); AdjustDown(p->a, p->size, 0); //左右子树还是小堆，直接调整行了 }5.获取堆顶的数据
DateType HeapTop(Heap*p) { assert(p); return p->a[0]; }6.堆的数据个数
int HeapSize(Heap*p) { assert(p); return p->size; }7.判空
bool HeapIsEmpty(Heap*p) { assert(p); return p->size == 0; }8.打印
void Print(Heap*p) { assert(p); for (int i = 0; i 9.销毁
void HeapDestory(Heap*p) { assert(p); free(p->a); p->a = NULL; p->capacity = p->size = 0; }10.测试
int main() { int num[] = { 12,15,17,23,10,25 }; int n = sizeof(num) / sizeof(num[0]); Heap a; //创建小堆 CreatHeap(&a,num, n); Print(&a); printf("\n"); //插入数据 HeapPush(&a, 1); Print(&a); //删除对顶的数据 HeapPop(&a); Print(&a); printf("\n"); //获取堆顶数据 int ret=HeapTop(&a); printf("The top date is %d\n",ret); //堆的数据个数 int number=HeapSize(&a); printf("The number of heap is %d\n", number); //销毁 HeapDestory(&a); return 0; }11.测试结果
12.用堆排序(降序)
int main() { DateType num[] = { 12,15,17,23,10,25 }; int n = sizeof(num) / sizeof(num[0]); HeapSort(num, n); for (int i = 0; i void HeapSort(int*num, int n) { //建小堆 for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(num, n, i); } int end = n - 1; while (end>0) { Swap(&num[0], &num[end]); AdjustDown(num, end, 0); --end; } }
以上就是C语言数据结构堆的基本操作实现的详细内容，更多请关注0133技术站其它相关文章！
