最大优先队列包含以下操作：
将元素x插入到S的集合中，等价于 ；
返回S中最大元素；
返回并且删除S中最大元素；
将元素x的关键字增加到key，要求 。
同样的，最小优先队列操作也包括： , , , 。只不过是对最小值进行操作。
在这里主要讨论最大优先队列，其应用很多，在共享计算机作业系统就是，类似于早期的unix主机，管理员root可以设置n个不同的用户，以及各个用户不同的操作权限，从主机那里接出多个终端，每个操作人员（程序员）在自己的工作终端 ，感觉像是自己拥有自己独立的作业主机一样，其实不是，通过一些任务调度来实现，其中就有任务等待执行相关队列，并且有各个任务有着自己优先级，以便确定调度执行具体任务，如果你学过操作系统相关知识，那么应该对系统调度有所了解。
当一个作业被完成或者被中断后，调度器会调用 来调用所有在队列中等待任务中优先级最高的任务执行，在新任务加入等待任务时会调用 加入任务等待队列，当某个任务等待时间过长时可通过 提高其优先级，从而减少等待时间。
下面是具体实现C程序源码：
#include <stdio.h>
#define NAGE_INFINIT -99999
#define parent(i) i/2
#define left(i) 2*i+1
#define right(i) 2*i+2
//get array of A first element
int heap_maximum(int A[]){ return A[0]}
/***********************************************
*
* function max_heapify()
*
* args
* A[] inttype save elements of heap
* i index of A
* heap_size real length of A
*
* ********************************************/
void max_heapify(int A[],int i,int heap_size){
int l,r,largest,temp
l=left(i)
r=right(i)
if((l<=heap_size)&&(A[l]>A[i]))
largest=l
else
largest=i
if((r<=heap_size)&&(A[r]>A[largest]))
largest=r
if(largest!=i){
temp=A[i]
A[i]=A[largest]
A[largest]=temp
max_heapify(A,largest,heap_size)
}
}
/*********************************************
*
* function heap_extract_max()
*
* args
* A[] inttype save elements of heap
* heap_size inttype the real length of A
*
* return max the parent node value
*
* ******************************************/
int heap_extract_max(int A[],int heap_size){
int max
if(heap_size<0)
return -1 //heap underflow
max=A[0] //parent node the max value of element
A[0]=A[heap_size]
heap_size--
/**************************************
* dajust binary heap(or tree) to make
* sure heap fo A true every times
*
* ************************************/
max_heapify(A,0,heap_size)
return max
}
/***********************************************
*
* function heap_increase_key()
*
* args
* A[] inttype save elemnts of heap
* i index of A
* key inserted element
*
* *********************************************/
void heap_increase_key(int A[],int i,int key){
int temp
if(key<A[i]){
printf("new key is smaller than current key\n")
return //over programming
}
A[i]=key
//p=parent(i)
while ((i>0)&&(A[parent(i)]<A[i])) {
temp=A[i]
A[i]=A[parent(i)]
A[parent(i)]=temp
i=parent(i)//update index of A
//p=parent(i)
}
}
/***************************************************
*
* function max_heap_insert()
*
* args
* A[] inttype save elements of A
* key inserted element to A
* heap_size real length of A
*
* **************************************************/
void max_heap_insert(int A[],int key,int heap_size){
heap_size+=1
A[heap_size]=NAGE_INFINIT
heap_increase_key(A,heap_size,key)
}
int main()
{
int heap_max,max,i,key
int A[11],Temp[11]
int heap_size=0
char c
while (1) {
scanf("%d",&A[heap_size])
c=getchar()
if(c=='\n')
break
heap_size++
}
//copy A to Temp
for(i=0i<=heap_sizei++)
Temp[i]=A[i]
//get heap maximum element
heap_max=heap_maximum(A)
printf("heap of A maximum element: %d\n",heap_max)
//copy Temp to A
for(i=0i<=heap_sizei++)
A[i]=Temp[i]
/*--extract maximum element--*/
max=heap_extract_max(A,heap_size)
printf("extract element: %d \n",max)
printf("new heap of A after extract maximum node\n")
for(i=0i<heap_sizei++)
printf("%d ",A[i])
printf("\n") //next line
//copy Temp to A
for(i=0i<=heap_sizei++)
A[i]=Temp[i]
/*--increase from A[i] to key--*/
printf("input i key ")
scanf("%d %d",&i,&key)
heap_increase_key(A,i,key)
for(i=0i<=heap_sizei++)
printf("%d ",A[i])
printf("\n")
//copy Temp to A
for(i=0i<=heap_sizei++)
A[i]=Temp[i]
/*--insert queueu--*/
key=0 //init key
printf("input key: ")
scanf("%d",&key)
max_heap_insert(A,key,heap_size)
for(i=0i<=heap_size+1i++)
printf("%d ",A[i])
printf("\n")
return 0
}
/****************************************
*
* input 16 14 10 8 7 9 3 2 4 1
* i: 8
* key: 15
*
* output in function main()
* **************************************/
其运行结果如下图：
欢迎留言交流，也感谢指正，一起进步。
# include "stdio.h"# include "malloc.h"
# include "stdlib.h"
typedef struct Queue
{
int data
int Priority
Queue * Next
}* PQUEUE
bool insert(PQUEUE p,int i, int j)
bool pop(PQUEUE p)
void sort(PQUEUE p)
int length = 0
PQUEUE pT
int main(void)
{
PQUEUE pH = (PQUEUE)malloc(sizeof(Queue))
insert(pH, 75, 8)
insert(pH, 54, 4)
insert(pH, 75, 6)
insert(pH, 23, 5)
insert(pH, 81, 4)
insert(pH, 65, 3)
insert(pH, 43, 4)
insert(pH, 34, 2)
sort(pH)
pop(pH)
pop(pH)
pop(pH)
pop(pH)
pop(pH)
pop(pH)
pop(pH)
pop(pH)
return 0
}
bool insert(PQUEUE p,int i, int j)
{
if(i>= 0 &&i<= 100 &&j>=0 &&j<=100)
{
PQUEUE pNew = (PQUEUE)malloc(sizeof(Queue))
if(length == 0)
{
pT = NULL
}
if(pT == NULL)
{
pT = p
}
if(NULL == pNew)
{
printf("动态内存分配失败~!")
exit(-1)
}
pNew->data = i
pNew->Priority = j
pT->Next = pNew
pNew->Next = NULL
pT = pNew
length++
return true
}
return false
}
PQUEUE p2
bool pop(PQUEUE p)
{
if(length != 0)
{
p2 = p
p = p->Next
printf("%d,", p->data)
printf("%d\n", p->Priority)
p2->Next = p->Next
length--
return true
}
return false
}
void sort(PQUEUE p)
{
if(length != 0)
{
PQUEUE w,q
int i, j, t1,t2
for(i=0,w=p->Nexti <length-1++i,w = w->Next)
{
for(j=i+1,q=w->Nextj <length++j,q = q->Next)
{
if(w->Priority <q->Priority)
{
t1 = w->data
w->data = q->data
q->data = t1
t2 = w->Priority
w->Priority = q->Priority
q->Priority = t2
}
}
}
}
return
}
/*
都满足你的要求了，以上是使用链表结构的队列
*/
