堆结构

2/10/2017来源:ASP.NET技巧人气:267

堆的主要操作:

*建立一个堆 *往堆里添加新元素 *访问最大/最小值 *删除最大/最小值

模板如下:

#include<cstdio> #define MAX_SIZE 100 int A[MAX_SIZE]={0,1,2,3,4,5,6,7,8,9},N=9; //下标从1开始 void downAdjustment(int A[],int idx);//向下调整 void buildHeap(){ int i; for(int i=N/2;i>=1;i--) downAdjustment(A,i); } void downAdjustment(int A[],int idx){ int leftChild= 2*idx; int rightChild= 2*idx+1; int max; if(leftChild > N) return; if( rightChild >N||(A[leftChild] > A[rightChild]) ) max=leftChild; else max=rightChild; if(A[idx] < A[max]){ int tmp=A[idx]; A[idx]= A[max]; A[max]=tmp; downAdjustment(A,max);//递归向下调整 } } //向上调整 void upAdjustment(int A[],int idx){ int parent= idx/2; if(parent < 1) return; if(A[idx] > A[parent]){ int tmp=A[idx]; A[idx]=A[parent]; A[parent]=tmp; upAdjustment(A,parent);//递归向上调整 } } //添加新元素 void addAElement(int ele){ A[++N] = ele; upAdjustment(A,N); } //访问最大值 int maxElement(){ return A[1]; } //删除最大值 void deleteMax(){ A[1]=A[N]; N--; downAdjustment(A,1); } int main(){ buildHeap(); for(int i=1;i<=N;i++) PRintf("%d ",A[i]); printf("\n--------\n\n"); addAElement(10); for(int i=1;i<=N;i++) printf("%d ",A[i]); deleteMax(); printf("\n---\n\n"); for(int i=1;i<=N;i++) printf("%d ",A[i]); return 0; }