C语言实现小根堆

迭代式建堆

#include<stdio.h>voidswap(int*a,int*b){inttemp=*a;*a=*b;*b=temp;}voiddown(int*nums,intsize,inti){for(intk=2*i+1;k<size;k=2*k+1){/* 父节点 (k - 1) / 2，左子节点 k，右子节点 k + 1 */printf_s("*************************************************************\r\n");printf_s("父节点i = %d, 左子节点k = %d, 右子节点k + 1 = %d\r\n",i,k,k+1);// 取左右子节点中较小的那一个if(k+1<size&&nums[k]>nums[k+1]){printf_s("nums[%d] > nums[%d] %d > %d k++\r\n",k,k+1,nums[k],nums[k+1]);k++;}if(nums[k]>nums[(k-1)/2]){printf_s("nums[%d] > nums[%d] %d > %d break\r\n",k,(k-1)/2,nums[k],nums[(k-1)/2]);printf_s("*************************************************************\r\n");break;}printf_s("nums[%d] < nums[%d] %d < %d swap\r\n",k,(k-1)/2,nums[k],nums[(k-1)/2]);swap(&nums[k],&nums[(k-1)/2]);for(intj=0;j<size;j++){printf("%d ",nums[j]);}printf_s("\r\n");for(intj=0;j<size;j++){printf("%d ",j);}printf_s("\r\n*************************************************************\r\n");}}voidInit(int*nums,intsize){for(inti=size/2-1;i>=0;i--){down(nums,size,i);}}intPop(int*nums,intsize){swap(&nums[0],&nums[size-1]);down(nums,size-1,0);returnnums[size-1];}voidPush(int*nums,intsize,intx){nums[size]=x;// 子节点小于父节点的值，交换值for(inti=size;i>=0&&nums[(i-1)/2]>nums[i];i=(i-1)/2){swap(&nums[(i-1)/2],&nums[i]);}}voiditerator(int*nums,intsize){for(inti=0;i<size;i++){printf("%d ",nums[i]);}printf("\n");}intmain(){intarr[]={9,8,7,6,5,4,3,2,1};intn=sizeof(arr)/sizeof(arr[0]);Init(arr,n);printf("Min Heap:\n");iterator(arr,n);Push(arr,n-1,0);iterator(arr,n);Pop(arr,n);iterator(arr,n);return0;}

运行结果

大根堆中的比较逻辑：如果父节点小于较大的子节点，交换两个节点
小根堆中的比较逻辑：如果父节点大于较小的子节点，交换两个节点
这是废话^~^

外部参考

C 语言实现海量数据 TopK 问题：小顶堆实战详解
C语言实现大根堆