堆的主要操作:
*建立一個堆 *往堆里添加新元素 *訪問最大/最小值 *刪除最大/最小值
模板如下:
#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++)新聞熱點
疑難解答
