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

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

1、C+实现堆排序示例目录堆的实现Heap.h堆的管理及接口Heap.c堆各个接口功能的实现test.c测试堆的实现Heap.h堆的管理及接口#include#include#includetypedefintHPDataType;typedefstructHeapHPDataType*a;intsize;intcapacity;Heap;voidAdjustDown(HPDataType*a,intn,introot);堆的向上调整算法voidAdjustUp(HPDataType*a,intchild);堆的初始化voidHeapInit(Heap*php,HPDataType*a,intn)

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

3、udeHeap.h堆向下调整算法建小堆voidAdjustDown(HPDataType*a,intn,introot)(intparent=root;intchild=parent*2+1;孩子超过数组下标结束while(childn)(/child始终左右孩子中小的那个if(achild+1achild&child+1n)防止没有右孩子+child;小的往上浮，大的往下沉if(achildparent则已满足小堆，直接breakelsebreak;堆的向上调整算法建小堆voidAdjustUptHPDataType*a,intchild)intparent=(child-1)/2;whil

4、e(child0)(if(achilda=(HPDataType*)malloc(n*Sizeof(HPDataType);if(php-a=NULL)(printf(mallocfailn);exit(-l);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=NULL;php-capacity=0;php-size=0;voidHeapPus

5、h(Heap*php,HPDataTypex)assert(php);if(php-size=php-capacity)HPDataType*tem=(HPDataType*)realloc(php-a,php-capacity*2*Sizeof(HPDataType);if(tem=NULL)(printf(reallocfailn);exit(-l);php-a=tem;php-capacity*=2;php-aphp-size=x;+php-size;AdjustUp(php-a,php-size-1);堆的删除voidHeapPop(Heap*php)assert(php);asser

6、t(php-sizeO);HPDataTypetern=php-aphp-size-1;php-aphp-size-1=php-aO;php-aO=tern;-php-size;AdjustDown(php-a,php-size,0);堆里的数据个数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测试#includeHeap.hvoidTestHeapO(intarr=27,28,65,25,15,34,19,49,18,37;Heaphp;Heaplnit(&hp,arr,sizeof(arr)sizeof(int);while(!HeapEmpty(&hp)(printf(%d,HeapTop(hp);HeapPop(&hp);prntf(n);HeapDestroy(8ihp);intmain(TestHeapO;return0;