最大优先队列包含以下操作：
将元素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
}
/*
都满足你的要求了，以上是使用链表结构的队列
*/
//短作业优先#include <stdio.h>
#include <malloc.h>
#define max 5
#define M 100
typedef float datatype
typedef struct node//单链表
{
char name[2]
datatype arrive //到达时间
datatype service//服务时间
datatype wait //等待时间
datatype begin //开始时间
datatype finish //结束时间
datatype cycle //周转时间
datatype right //带权周转时间
struct node *next
}Lnode
//输入进程信息，尾插入法将进程节点插入单链表
void input(node *h)
{
Lnode *p
p=(Lnode*)malloc(sizeof(Lnode))
printf("进程： ")
scanf("%s",p->name)
printf("到达时间： ")
scanf("%f",&p->arrive)
printf("服务时间： ")
scanf("%f",&p->service)
p->next=NULL
while(h->next!=NULL)
{
h=h->next
}
p->next=h->next
h->next=p
}
//实现短进程优先
void program(Lnode *&h)
{
int j,k=0,i=1
datatype min,temp
Lnode *p,*q
p=h->next
p->begin=p->arrive
p->wait=p->begin-p->arrive //等待时间开始时间-到达时间
p->finish=p->begin+p->service//完成时间=开始时间+服务时间
p->cycle=p->service+p->wait //周转时间=服务时间+等待时间
p->right=p->cycle/p->service //带权周转时间=周转时间/服务时间
temp=p->finish
//输出第一个进程的信息
printf("%s\t%3.1f\t%3.1f\t%3.1f\t%3.1f\t %3.1f \t%3.1f\t%3.1f\n",p->name,p->arrive,p->service,p->wait,p->begin,p->finish,p->cycle,p->right)
p=p->next
j=0
while(i<max)//查找最短进程，从第二个进程开始
{
min=M
while(p!=NULL)
{
if(p->arrive<temp&&p->service<min)
{
min=p->service
p=p->next
j++
}
else p=p->next
}
p=h->next //p指向首节点
//找出该节点（进程），并输出该进程信息
while (k<j-1 &&p!=NULL)
{
k++
p=p->next
}
q=p->next
q->begin=temp
q->wait=q->begin-q->arrive
q->finish=q->begin+q->service
q->cycle=q->service+q->wait
q->right=q->cycle/q->service
//输出进程信息
printf("%s\t%3.1f\t%3.1f\t%3.1f\t%3.1f\t %3.1f \t%3.1f\t%3.1f\n",q->name,q->arrive,q->service,q->wait,q->begin,q->finish,q->cycle,q->right)
temp=q->finish
p->next=q->next //删除该节点
free(q) //释放该节点
i++
p=h->next//p指向首节点
j=1
}
}
void main()
{
Lnode *h,*p
h=(Lnode*)malloc(sizeof(Lnode))
h->next=NULL
char *b[8]={"进程","达到时间","服务时间","等待时间","开始时刻","结束时刻","周转时间","带权周转时间"}
int i=0
printf("输入进程信息：\n")
while(i<max)
{
input(h)
i++
}
printf("\n")
p=h->next
while(p!=NULL) //输出单链表
{
printf("进程:%s到达时间:%3.1f 服务时间:%3.1f\n",p->name,p->arrive,p->service)
p=p->next
}
printf("\n")
printf("%s %s %s %s %s %s %s %s\n",b[0],b[1],b[2],b[3],b[4],b[5],b[6],b[7])
program(h)
}
