C语言数据结构堆的基本操作实现
程序员文章站
2022-06-21 14:10:11
目录1.基本函数实现a.代码1(向下调整)b.代码2(向上调整)c.代码3(交换)2.建堆 3.插入数据4. 删除数据5.获取堆顶的数据6.堆的数据个数7.判空8.打印9.销毁10.测试11.测试结果...
1.基本函数实现
a.代码1(向下调整)
void adjustdown(datetype*a, int n, int parent) { int child = parent * 2 + 1; while (child<n) { if ((child+1) < n && a[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)<n是防止越界的,因为不能保证有右孩子。
b.代码2(向上调整)
void adjustup(datetype*a , int child) { 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; } } }
注意:while里面的条件语句是不能够写成(parent<0),因为当child==0时,parent=(child - 1) / 2,parent==0,再次进入循环不满足a[child] < a[parent],恰好跳出循环。如果写成(a[child] <= a[parent])就死循环了
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); //左右子树还是小堆,直接调整行了 }
把堆顶的数据与最后一个数据交换,再次调整size-1个数据。
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 < p->size; i++) { printf("%d ", (p->a)[i]); } printf("\n"); int count = 0;//计数 int levelsize = 1; for (int i = 0; i < p->size; i++) { printf("%d ", p->a[i]); ++count; if (count == levelsize) { printf("\n"); levelsize *= 2; count = 0;//重新计数 } } printf("\n"); }
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.用堆排序(降序)
a.代码1
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 < n; i++) { printf("%d ", num[i]); } printf("\n\n"); return 0; }
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; } }
运行结果
堆的基本操作今天就分享在到这里了,谢谢你的浏览,如果对你有帮助的话请大家以后多多支持!
下一篇: python Xpath语法的使用