小顶堆的递归构建
道理很简单,顶上是最小的,比左右子树都小,在整个树上都成立。
代码如下:
void swap(int &a,int &b) { if(a!=b) { int temp; temp=a; a=b; b=temp; } } void show(int *a ,int n)//显示数组 { cout<<"一共"<<a[0]<<"个元素"<<endl; for(int i=1;i<n;i++) { cout<<*(a+i)<<" "; } cout<<endl; } ////堆的构建 //// 堆a[0]用来存储堆中元素的个数 父节点i 左孩子(2*i) 有孩子(2*i+1) void heapfy(int a[],int i)//3,1,2,5,10,4 { int l=2*i,r=2*i+1; int temp=i; if(l>a[0]&&r>a[0]) // { return ; } if((l<=a[0])&&a[temp]>a[l] ) { temp=l; } if((r<=a[0])&&a[temp]>a[r]) { temp=r; } if(i!=temp)//将2个儿子中的 最小的和父亲比 ,最小的放在父节点上 { swap(a[i],a[temp]); } heapfy(a,l); //分治左子树 heapfy(a,r); //分治右子树 } void heap(int a[]) { for(int i=a[0]/2;i>0;i--)//要从中间开始 向前 { heapfy(a,i); } } int main(int argc, char* argv[]) { int a[9] = { 8,19,3,1,5,0,10,2}; int h[20]={0}; int n=9; h[0]=n; for(int j=n;j>0;j-- ) { h[j]=a[j-1]; } heap(h); show(h,10); return 0; }
代码贴完 ,可能有问题 ,求挑错,求打脸。