最大优先级队列有着以下操作:
1.返回最大值:heap_maximum
2.去掉最大值并返回:heap_extract_max
3.将i的关键值增加到key:heap_increase_key
4.向优先队列中插入一个结点:max_heap_insert
算法代码及测试代码如下:
#include <stdio.h> #include <conio.h> #include <stdlib.h> #define MAX 1000 //函数原型 void max_heapify(int A[],int i,int length); void swap(int *a,int *b); int heap_maximum(int A[]); void build_max_heap(int A[],int n); int heap_extract_max(int A[],int &n); int parent(int i); void heap_increase_key(int A[],int i,int key); void max_heap_insert(int A[],int &n,int key); int main() { int test[MAX]={-1,5,4,6,9,8,7,2,3,1,10};//除test[0]外,10个测试数据 int n=10; build_max_heap(test,10);//建立大顶堆 int result=heap_extract_max(test,n); max_heap_insert(test,n,111); for(int i=1;i<11;i++) printf("%d ",test[i]); getch(); } //保持大顶堆性质 void max_heapify(int A[],int i,int length) { int largest=i; //最大值的下标 int sub_left=i<<1;//左子树根结点的坐标 int sub_right=sub_left+1;//右子树根结点的坐标 if(sub_left<=length && A[i]<A[sub_left]) largest=sub_left; if(sub_right<=length && A[largest]<A[sub_right]) largest=sub_right; if(largest!=i) { swap(&A[largest],&A[i]); max_heapify(A,largest,length); } } //建堆 void build_max_heap(int A[],int n) { for(int i=(n>>1);i>=1;i--) max_heapify(A,i,n); } //交换 void swap(int *a,int *b) { int temp=*a; *a=*b; *b=temp; } //返回最大值 int heap_maximum(int A[]) { return A[1]; } //去掉并返回最大值 int heap_extract_max(int A[],int &n) { int max=A[1]; A[1]=A[n];//将最后一个数放到最前 n--; max_heapify(A,1,n); return max; } //将i的关键值增加到key,key应该大于A[i] void heap_increase_key(int A[],int i,int key) { if(A[i]>=key) printf("new key is smaller than or equal to current key!"); else { A[i]=key; while(i>1 && A[i]>A[parent(i)]) { swap(&A[i],&A[parent(i)]); i=parent(i); } } } //求parent结点的关键值 int parent(int i) { return i/2; } //向优先队列中插入一个结点 void max_heap_insert(int A[],int &n,int key) { A[++n]=-INT_MAX; heap_increase_key(A,n,key); }总结:最大优先级队列主要用于作业调度,当某一作业完成或被终端时,选择出具有最高优先级的作业。相对的还有最小优先级队列。