//交互main()函数
/***************************************************test_MPQ.c**********************************************/
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "MaxPriorityQueue.h"
int main(void)
{ //建立最大堆
extern int heap_size;//声明使用具有文件作用域、外部链接、静态存储的队列大小的变量
puts("How many elements of your max priority queue");
scanf("%d",&heap_size);
//读取换行符
while(getchar()!='\n')
continue;
int *queue=(int *)malloc(heap_size*sizeof(int));
srand(time(0));
for(int i=0;i<heap_size;i++)
queue[i]=rand()%heap_size;
build_max_heap(queue);
puts("your initial max heap");
for(int i=0;i<heap_size;i++)
printf("%7d",queue[i]);
// 四项操作：返回最大关键字、提取最大关键字、增加关键字、插入关键字
printf("\nplease choose operation\na. return maximum");
printf(" b.extract max\nc.increase key d.insert key\n");
char ch;
while((ch=getchar())!='q')//while语句来控制操作的开始与结束
{
//if分枝结构处理操作请求
if(ch=='a')
printf("heap maximum:%d\n",heap_maximum(queue));
else if(ch=='b')
{ printf("extract maximum:%d\n",heap_extract_max(queue));
puts("now ,the heap");
for(int i=0;i<heap_size;i++)
printf("%7d",queue[i]);
putchar('\n');
}
else if(ch=='c')
{ puts("enter the element's index you want to increase\n" );
int index;
scanf("%d",&index);
printf("the key is %d\n",queue[index]);
puts("enter the new value of the key");
int new_key;
scanf("%d",&new_key);
heap_increase_key(queue,index,new_key);
puts("now the max priority queue:");
for(int i=0;i<heap_size;i++)
printf("%7d",queue[i]);
putchar('\n');
}
else if (ch=='d')
{ puts("enter the value you to insert");
int key;
scanf("%d",&key);
max_heap_insert(queue,key);
puts("now the max priority queue:");
for(int i=0;i<heap_size;i++)
printf("%7d",queue[i]);
putchar('\n');
}
while(getchar()!='\n')
continue;
puts("please enter a b c or d(q to quit)");
}
puts("Bye!");
free(queue);
}
/*****************************************MaxPriorityqueue.c*******************************************************/
//支持操作的函数文件
#include <stdio.h>
#include <stdlib.h>
static void error(char *Wrong_Message);
int max_heapify(int *,int );
int heap_size; //定义具有文件作用域、外部链接，的静态变量，操作队列的过程，记录优先队列的大小
//返回最大关键字
int heap_maximum(int arr[])
{ return arr[0];
}
//提取最大关键字
int heap_extract_max(int arr[])
{
int max;
if (heap_size<1)
error("heap underflow");
max=arr[0];
arr[0]=arr[heap_size-1];
heap_size--;
max_heapify(arr,0);
return max;
}
//增加关键字的优先度（值）
int heap_increase_key(int arr[],int i,int key)
{ if( key<arr[i])
error("new key is smaller than current key");
arr[i]=key;
while(i>0&&arr[i/2]<arr[i])
{ arr[i]=arr[i/2];
arr[i/2]=key;
i/=2;
}
}
//插入关键字
max_heap_insert(int arr[],int key)
{ heap_size++;
arr[heap_size]=-100000;
heap_increase_key(arr,heap_size,key);
}
//该文件私有的错误处理函数
static void error(char *Wrong_Message)
{
while(*Wrong_Message!='\0')
{ putchar(*Wrong_Message);
Wrong_Message++;
}
putchar('\n');
exit(EXIT_FAILURE);
}
//建立最大堆
int build_max_heap(int *pt)
{ for(int i=(heap_size-1)/2;i>=0;i--)
max_heapify(pt,i);
}
//插入单个元素，并保持堆性质的函数int max_heapify(int *pt,int i)
{ int largest;
int l,r;
int temp=pt[i];
l=2*i+1;
r=2*i+2;
if(l<heap_size&&pt[l]>pt[i])
largest=l;
else
largest=i;
if(r<heap_size &&pt[r]>pt[largest])
largest=r;
if(largest!=i)
{ pt[i]=pt[largest];
pt[largest]=temp;
max_heapify(pt,largest);
}
}
/******************************************MaxPriorityqueue.h*****************************************/
//h文件,函数原型
int heap_maximum(int []);
int heap_increase_key(int [],int ,int);
int max_heap_insert(int [],int);
int heap_extract_max(int []);
int build_max_heap(int *);
int max_heapify(int *,int );