本文共 2281 字，大约阅读时间需要 7 分钟。

一、描述：

A priority queue is a data structure formaintaining a set S of elements, each with an associated value called a key. A max-priorityqueue supports the following operations.

. INSERT(S, x) inserts the element x into the set S. This operation could be written as S← S∪ {

. MAXIMUM(S) returns the element of S with the largest key.

. EXTRACT-MAX(S) removes and returns the element of S with the largest key.

. which is assumed to be atleast as large as x's current key value.

二、 数据输入

A=<15，13，9，5，12，8，7，4，0，6，2，1>

三、 结果输出

执行INSERT(A, 10)，EXTRACT-MAX(A)，将结果输出到文件output.txt。

四、代码：

#include
   
    #include
    
     #define N 15int a[N],size,for_size;void up_down_maxHeap(int i){    int l=2*i;    int r=2*i+1;    int maxx=i;    if(l<=size && a[l]>a[i])    maxx=l;    else if(r<=size && a[r]>a[maxx])    maxx=r;    if(maxx!=i)    {        int tmp=a[maxx];        a[maxx]=a[i];        a[i]=tmp;        up_down_maxHeap(maxx);    }}void buildMaxHeap(){    for(int i=1;i<=for_size;i++)    {        up_down_maxHeap(i);    }    printf("建好的大顶堆序列：");    for(int i=1;i<=size;i++)    printf("%d ",a[i]);    printf("\n");}void down_up_maxHeap(int i){    int father=i/2;    if(a[father]
     
      0)    {        int tmp=a[father];        a[father]=a[i];        a[i]=tmp;        down_up_maxHeap(father);    }}void insert(int x){    size++;    a[size]=x;    down_up_maxHeap(size);    printf("插入元素%d后的堆序列:",x);    for(int i=1;i<=size;i++)        printf("%d ",a[i]);    printf("\n");}void maximum(){    printf("堆中最大的元素是:%d\n",a[1]);}void extract_max(){    int tmp=a[1];    a[1]=a[size];    a[size]=tmp;    up_down_maxHeap(1);    size--;    printf("删除最大元素%d后的堆序列:",tmp);    for(int i=1;i<=size;i++)    printf("%d ",a[i]);    printf("\n");}void increase_key(int x,int k){    int tmp=a[x];    a[x]=k;    down_up_maxHeap(x);    printf("将%d位置的元素%d增加到%d后的堆序列:",x,tmp,k);    for(int i=1;i<=size;i++)    printf("%d ",a[i]);    printf("\n");}int main(){    int x,k;    freopen("heapInput.txt","r",stdin);    freopen("heapOutput.txt","w",stdout);    scanf("%d",&size);    for(int i=1;i<=size;i++)    scanf("%d",&a[i]);    for_size=(size%2==0)?size/2:size/2+1;    buildMaxHeap();    scanf("%d",&x);    insert(x);    maximum();    extract_max();    scanf("%d%d",&x,&k);    increase_key(x,k);    return 0;}
     
    
   

转载地址：http://nhddi.baihongyu.com/