C语言数据结构堆的基本操作实现

第C语言数据结构堆的基本操作实现目录1.基本函数实现a.代码1(向下调整)b.代码2(向上调整)c.代码3(交换）2.建堆

3.插入数据4.删除数据5.获取堆顶的数据6.堆的数据个数7.判空8.打印9.销毁10.测试11.测试结果12.用堆排序(降序)

1.基本函数实现

a.代码1(向下调整)

voidAdjustDown(DateType*a,intn,intparent)

intchild=parent*2+1;

while(childn)

if((child+1)na[child]a[child+1])

++child;

if(a[parent]a[child])

Swap(a[parent],a[child]);

parent=child;

child=parent*2+1;

else

break;

}

注意:if里面的条件语句(child

+1)n是防止越界的，因为不能保证有右孩子。

b.代码2(向上调整)

voidAdjustUp(DateType*a,intchild)

intparent=(child-1)/2;

while(child0)

if(a[child]a[parent])

Swap(a[child],a[parent]);

child=parent;

parent=(child-1)/2;

else

break;

}

注意:while里面的条件语句是不能够写成(parent0)，因为当child==0时，parent=(child-1)/2,parent==0,再次进入循环不满足a[child]a[parent]，恰好跳出循环。如果写成(a[child]=a[parent])就死循环了

c.代码3(交换）

voidSwap(DateType*p1,DateType*p2)

DateTypetmp=*p1;

*p1=*p2;

*p2=tmp;

}

2.建堆

voidCreatHeap(Heap*p,DateType*num,intn)

assert(p);

p-a=(DateType*)malloc(n*sizeof(DateType));

if(p-a==NULL)

printf("mallocfailed\n");

exit(-1);

memcpy(p-a,num,n*sizeof(DateType));

p-size=n;

p-capacity=n;

//建小堆

for(inti=(n-1-1)/2;ii--)

AdjustDown(p-a,p-size,i);

}

3.插入数据

voidHeapPush(Heap*p,DateTypex)

assert(p);

if(p-size==p-capacity)

DateType*tmp=(DateType*)realloc(p-a,(p-capacity)*2*sizeof(DateType));

if(tmp==NULL)

printf("reallocfailed\n");

exit(-1);

(p-capacity)*=2;

p-a[p-size]=x;

++(p-size);

//向上调整

AdjustUp(p-a,p-size-1);

}

4.删除数据

voidHeapPop(Heap*p,DateTypex)

assert(p);

Swap(p-a[0],p-a[p-size-1]);

--(p-size);

AdjustDown(p-a,p-size,0);

//左右子树还是小堆，直接调整行了

}

把堆顶的数据与最后一个数据交换，再次调整size-1个数据。

5.获取堆顶的数据

DateTypeHeapTop(Heap*p)

assert(p);

returnp-a[0];

}

6.堆的数据个数

intHeapSize(Heap*p)

assert(p);

returnp-size;

}

7.判空

boolHeapIsEmpty(Heap*p)

assert(p);

returnp-size==0;

}

8.打印

voidPrint(Heap*p)

assert(p);

for(inti=0;ip-size;i++)

printf("%d",(p-a)[i]);

printf("\n");

intcount=0;//计数

intlevelsize=1;

for(inti=0;ip-size;i++)

printf("%d",p-a[i]);

++count;

if(count==levelsize)

printf("\n");

levelsize*=2;

count=0;//重新计数

printf("\n");

}

9.销毁

voidHeapDestory(Heap*p)

assert(p);

free(p-

p-a=NULL;

p-capacity=p-size=0;

}

10.测试

intmain()

intnum[]={12,15,17,23,10,25};

intn=sizeof(num)/sizeof(num[0]);

Heapa;

//创建小堆

CreatHeap(a,num,n);

Print(

printf("\n");

//插入数据

HeapPush(a,1);

Print(

//删除对顶的数据

HeapPop(

Print(

printf("\n");

//获取堆顶数据

intret=HeapTop(

printf("Thetopdateis%d\n",ret);

//堆的数据个数

intnumber=HeapSize(

printf("Thenumberofheapis%d\n",number);

//销毁

HeapDestory(

return0;

}

11.测试结果

12.用堆排序(降序)

a.代码1

intmain()

DateTypenum[]={12,1