(新)C++实现堆排序示例.docx

《(新)C++实现堆排序示例.docx》由会员分享，可在线阅读，更多相关《(新)C++实现堆排序示例.docx（11页珍藏版）》请在第一文库网上搜索。

1、C+实现堆排序示例目录堆的实现He叩.h堆的管理及接口HeaP.c堆各个接口功能的实现test.c测试堆的实现He叩.h堆的管理及接口inc1udeinc1udeinc1udetypedefintHPDataType;typedefstructHeap(HPDataType*a;intsize;intcapacity;Heap;voidAdjustDown(HPDataType*a,intn,introot);堆的向上调整算法voidAdjuStUp(HPDataType*a,intchi1d);堆的初始化voidHeapInit(Heap*phpzHPDataType*azintn);堆的销

2、毁voidHeapDestroy(Heap*php);堆的插入voidHeapPush(Heap*php,HPDataTypex);堆的删除voidHeapPop(Heap*php);堆里的数据个数intHeapSize(Heap*php);判断堆是否为空intHeapEmpty(Heap*php);取堆顶数据HPDataTypeHeapTop(Heap*php);HeaP.c堆各个接口功能的实现堆的插入：将X插入下标为size的位置，+size然后使用向上调整算法调整堆的删除(删栈顶数据)：将栈顶数据和下标为SiZe-I位置的数据交inc1udeHeap.h堆向下调整算法建小堆voidAdj

3、ustDown(HPDataType*a,intn,introot)intparent=root;intchi1d=parent*2+1;孩子超过数组下标结束whi1e(chi1dn)/chi1d始终左右孩子中小的那个if(achi1d+1achi1d&chi1d+1n)防止没有右孩子+chi1d;小的往上浮，大的往下沉if(achi1dparent则已满足小堆，直接breake1se(break;)堆的向上调整算法建小堆voidAdjuStUp(HPDataType*azintchi1d)(intparent=(chi1d-1)/2;whi1e(chi1d0)(if(achi1da=(HPD

4、ataType*)ma11oc(n*Sizeof(HPDataType);if(php-a=NU11)(printf(,ma11ocfai1n);exit(-1);for(inti=0;iai=ai;)建堆for(inti=(n-2)/2;i=0;-i)(AdjustDown(php-a,n,i);)php-capacity=n;php-size=n;堆的销毁voidHeapDestroy(Heap*php)(assert(php);free(php-a);php-a=NU11;php-capacity=O;php-size=O;voidHeapPush(Heap*php,HPDataType

5、x)assert(php);if(php-size=php-capacity)(HPDataType*tern=(HPDataType*)rea11oc(php-a,php-capacity*2*Sizeof(HPDataType);if(tern=NU11)(printf(,rea11ocfai1n);exit(-1);php-a=tern;php-capacity*=2;)php-aphp-size=x;+php-size;AdjustUp(php-a,php-size-1);堆的删除voidHeapPop(Heap*php)assert(php);assert(php-sizeO);HP

6、DataTypetern=php-aphp-size-1;php-aphp-size-1=php-aO;php-aO=tem;-php-size;AdjustDown(php-a,php-sizez0);堆里的数据个数intHeapSize(Heap*php)(assert(php);returnphp-size;判断堆是否为空为空返回1,不为空返回0intHeapEmpty(Heap*php)(assert(php);returnphp-size=071:0;取堆顶数据HPDataTypeHeapTop(Heap*php)assert(php);assert(php-size0);returnphp-a0;test.c测试inc1udeHeap.hvoidTestHeapO(intarr=27,28,65,25,15,34z19z49,18z37;Heaphp;HeaPInit(&hp,arr,sizeof(arr)sizeof(int);whi1e(!HeapEmpty(Sihp)(printf(,%d,zHeaPTOP(&hp);HeaPPOP(&hp);)printf(,n);HeapDestroy(Sihp);intmain()(TestHeapO;return0;)