(新)C++实现堆排序示例.docx
C+实现堆排序示例目录堆的实现Heap.h堆的管理及接口Heap.c堆各个接口功能的实现test.c测试堆的实现Heap.h堆的管理及接口#include<stdio.h>#include<stdlib.h>#include<assert.h>typedefintHPDataType;typedefstructHeapHPDataType*a;intsize;intcapacity;Heap;voidAdjustDown(HPDataType*a,intn,introot);堆的向上调整算法voidAdjustUp(HPDataType*a,intchild);"堆的初始化voidHeapInit(Heap*php,HPDataType*a,intn);堆的销毁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,使用向下调整算法调整#include"Heap.h堆向下调整算法建小堆voidAdjustDown(HPDataType*a,intn,introot)(intparent=root;intchild=parent*2+1;孩子超过数组下标结束while(child<n)(/child始终左右孩子中小的那个if(achild+1<achild&&child+1<n)防止没有右孩子+child;小的往上浮，大的往下沉if(achild<aparent)inttern=aparent;aparent=achild;achild=tem;parent=child;child=parent*2+1;中途child>parent则已满足小堆，直接breakelsebreak;堆的向上调整算法"建小堆voidAdjustUptHPDataType*a,intchild)intparent=(child-1)/2;while(child>0)(if(achild<aparent)inttem=aparent;aparent=achild;achild=tem;child=parent;parent=(child-1)/2;else(break;"堆的初始化voidHeapInit(Heap*php,HPDataType*a,intn)assert(php);assert(a);php->a=(HPDataType*)malloc(n*Sizeof(HPDataType);if(php->a=NULL)(printf("mallocfailn");exit(-l);for(inti=0;i<n;i+php->ai=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;voidHeapPush(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);assert(php->size>O);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->size>0);returnphp->a0;test.c测试#include"Heap.h"voidTestHeapO(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;
