C语言实现小根堆

迭代式建堆#includestdio.hvoidswap(int*a,int*b){inttemp*a;*a*b;*btemp;}voiddown(int*nums,intsize,inti){for(intk2*i1;ksize;k2*k1){/* 父节点 (k - 1) / 2左子节点 k右子节点 k 1 */printf_s(*************************************************************\r\n);printf_s(父节点i %d, 左子节点k %d, 右子节点k 1 %d\r\n,i,k,k1);// 取左右子节点中较小的那一个if(k1sizenums[k]nums[k1]){printf_s(nums[%d] nums[%d] %d %d k\r\n,k,k1,nums[k],nums[k1]);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(intj0;jsize;j){printf(%d ,nums[j]);}printf_s(\r\n);for(intj0;jsize;j){printf(%d ,j);}printf_s(\r\n*************************************************************\r\n);}}voidInit(int*nums,intsize){for(intisize/2-1;i0;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(intisize;i0nums[(i-1)/2]nums[i];i(i-1)/2){swap(nums[(i-1)/2],nums[i]);}}voiditerator(int*nums,intsize){for(inti0;isize;i){printf(%d ,nums[i]);}printf(\n);}intmain(){intarr[]{9,8,7,6,5,4,3,2,1};intnsizeof(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语言实现大根堆