堆结构

2019-11-14 10:05:48

字体：大中小

来源：转载

供稿：网友

堆的主要操作:

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

#include<cstdio>#define MAX_SIZE 100int 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;}

上一篇：OJ 7219 复杂的整数划分问题__动态规划

下一篇：2.4