当前位置：首页 > news >正文

二叉树中堆的数据结构

news 2026/6/18 16:57:24

堆的概念和结构

如果有一个关键码的集合K = {k1 ，k2 ，k3 ，…，kn }，把它的所有元素按完全二叉树的顺序存储方式存储
在一个一维数组中，（i为下标）并满足：ki <= k(2i+1)且 ki<= k(2i+2)(ki >=k(2i+1) 且 ki>=k(2i+2) ) i = 0，1，2…，则称为小堆(或大堆)。将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。
堆的性质：

堆中某个结点的值总是不大于或不小于其父结点的值；
堆总是一棵完全二叉树。

下面是大堆的示例图：

堆的代码实现

//堆的初始化voidHpInit(Hp*php){assert(php);php->a=NULL;php->size=php->capacity=0;}//堆的销毁voidHpDestroy(Hp*php){assert(php);php->a=NULL;php->size=php->capacity=0;}//交换函数voidSwap(int*p1,int*p2){inttmp=*p1;*p1=*p2;*p2=tmp;}//向上调整voidAdjustUp(HpData*a,intchild){assert(a);intparent=(child-1)/2;while(child>0){if(a[child]<a[parent]){Swap(&a[child],&a[parent]);child=parent;parent=(child-1)/2;}else{break;}}}//堆的插入（向上调整版）voidHpPush(Hp*php,HpData x){assert(php);if(php->capacity==php->size){intnewcapacity=php->capacity==0?4:2*php->capacity;HpData*tmp=(int*)realloc(php->a,newcapacity*sizeof(HpData));if(tmp==NULL){perror("realloc fail!");return;}php->a=tmp;php->capacity=newcapacity;}php->a[php->size]=x;php->size++;AdjustUp(php->a,php->size-1);}// 堆数据的打印voidHpPrint(Hp*php){for(inti=0;i<php->size;i++){printf("%d ",php->a[i]);}printf("\n");}//向下调整voidAdjustDown(HpData*a,intparent,intsize){assert(a);intchild=2*parent+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=2*parent+1;}else{break;}}}//堆的插入（向下调整版）voidHpPush2(Hp*php,HpData x){assert(php);if(php->capacity==php->size){intnewcapacity=php->capacity==0?4:2*php->capacity;HpData*tmp=(int*)realloc(php->a,newcapacity*sizeof(HpData));if(tmp==NULL){perror("realloc fail!");return;}php->a=tmp;php->capacity=newcapacity;}php->a[php->size]=x;php->size++;AdjustDown(php->a,0,php->size);}//判空boolHpEmpty(Hp*php){if(php->a==NULL){returntrue;}else{returnfalse;}}//取堆顶数据HpDataHpTop(Hp*php){assert(php);returnphp->a[0];}//删除堆顶voidHpPop(Hp*php){Swap(&php->a[0],&php->a[php->size-1]);php->size--;AdjustDown(php->a,0,php->size);}

堆排序

通过上面的介绍，我们已经了解了堆是如何实现的，以及如何建立大堆和小堆
所以接下来我们可以通过上面完成的向上和向下调整建堆来实现堆排序

//向上调整建堆voidHpSort1(){intarr[]={4,6,1,7,9,8,2,5};//降序 先建小堆for(inti=0;i<sizeof(arr)/sizeof(int);i++){AdjustUp(arr,i);}intend=sizeof(arr)/sizeof(int)-1;while(end>0){Swap(&arr[0],&arr[end]);AdjustDown(arr,0,end);end--;}for(inti=0;i<sizeof(arr)/sizeof(int);i++){printf("%d ",arr[i]);}}//向下调整建堆voidHpSort2(){intarr[]={4,6,1,7,9,8,2,5};intn=sizeof(arr)/sizeof(int);intend=n;for(inti=(n-1-1)/2;i>=0;i--){AdjustDown(arr,i,n);}while(end>0){Swap(&arr[0],&arr[end-1]);AdjustDown(arr,0,end-1);--end;}for(inti=0;i<sizeof(arr)/sizeof(int);i++){printf("%d ",arr[i]);}}intmain(){HpSort1();printf("\n");HpSort2();return0;}