赞
踩
堆可以定义为一颗二叉树,树的节点包含键(每个节点一个键),并且满足下面两个条件:
下面这个就不是堆,因为不是完全二叉树
下面这个也不是堆,堆的节点比子节点大,4比5小
下面这个是堆
构造堆有两种方法,一种是自底向上堆构造;另一种是自定向下堆构造。
对于堆来说,每一个父母节点的值都要大于子女节点。所以从最后一个父母节点开始,一直到根节点,判断子女节点是否比父母节点的值小,如果大,则将交换父母节点和子女节点的值。
以2,9,7,6,5,8为例:
自顶向下堆构造算法的效率低,就是通过把新的键连续插入预先构造好的堆,然后将其值与父母进行比较直至根节点或值小于父母节点时,来构造一个新堆。
比如在下面的堆中插入9:
最大堆就是父节点比子节点大,最小堆就是父母节点比子节点小。
这里以
以2,9,7,6,5,8为例
#include <stdio.h> int num; void BuildHeap(int A[],int i,int N) //构造堆 { int c,temp; for (temp=A[i];2*i<=N;i=c) //temp记录下父母节点的值,c为一个子女节点 { c=2*i; if(c<N&& A[c+1]>A[c])//找到最大的子女节点 ++c; if(temp<A[c]) //父母节点值等于子女节点中大的 A[i]=A[c]; else break; } A[i]=temp;//对被交换的子女节点赋值 比如在2 9 8 6 5 7中9和2交换后,2需要和6再进行交换,最后只需要对6最开始的位置赋值2就行 } void Heapsort(int a[]) //排序 { int i,temp; for(i=num/2;i>=1;i--) //从最后一个父母节点开始,知道根节点 { BuildHeap(a,i,num); } for(i=num;i>0;i--) //删除根节点后,重新构造堆 { temp=a[1]; a[1]=a[i]; a[i]=temp; BuildHeap(a,1,i-1); } } int main() { printf("请输入要排序的数的个数:"); scanf("%d",&num); int i,a[num+1]; printf("请输入元素:"); for(i=1;i<=num;i++) scanf("%d",&a[i]); Heapsort(a); for(i=1;i<=num;i++) printf("%d ",a[i]); }
参考书籍:算法设计与分析基础
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。