优先队列

    队列可以分为FIFO队列和优先队列，优先队列也可以分为最大优先队列和最小优先队列。优先队列可以使用堆来实现，在一个堆结构中，优先队列的查找，插入，删除操作，都可以在O(lgn)的时间内完成。优先队列的常见使用是操作系统的作业调度，每当发生中断时，操作系统会从优先队列中选取一个优先级别最高的作业执行。下面是用最小堆实现的最小优先队列：

# include <iostream>
using namespace std;
# include <stdlib.h>
# define MIN -1
# define MAXSIZE 100
typedef struct priority_queue{
int *arr;
int size;
int capicity;
}pq;
int main()
{   int isempty(pq *T);
	int isfull(pq *T);
	pq* init(pq *T);
	pq* insert(pq *T,int x);
	int delmin(pq *T);
	int top(pq *T);
	
	pq *T=0;
	T=init(T);
	for(int i=0;i<10;i++)
		T=insert(T,i+1);
	cout<<delmin(T)<<endl;
	cout<<isfull(T)<<endl;
	cout<<isempty(T)<<endl;
system("pause");
return 0;
}

pq* init(pq *T)  //优先队列初始化
{
	T=(pq *)malloc(sizeof(pq));
	T->size=0;
	T->capicity=MAXSIZE;
	T->arr=(int *)malloc((MAXSIZE+1)*sizeof(pq));
	T->arr[0]=MIN;
	return T;
}
int isfull(pq *T)   //判断队列是否已满
{
	return T->size >=MAXSIZE;
}
pq* insert(pq *T,int x)   //插入元素
{
	if(isfull(T))
		return NULL;
	int i;
	for(i=++T->size;T->arr[i/2]>x;i/=2)
		T->arr[i]=T->arr[i/2];
	T->arr[i]=x;
	return T;
}

int isempty(pq *T)   //判断队列是否为空
{
	return T->size==0;
}



int delmin(pq *T)    //删除最小元素
{
	if(isempty(T))
		return -1;
	int min=T->arr[1];
	int last=T->arr[T->size--];
	int i,child;
	for(i=1;2*i<=T->size;i=child)
	{
	child=2*i;
	if(child!=T->size&&T->arr[child+1]<T->arr[child])
		child++;
	if(T->arr[child]<last)
		T->arr[i]=T->arr[child];
	else 
		break;
	}
	T->arr[i]=last;
	return min;

}

int top(pq *T)   //返回堆顶元素
{
	return T->arr[T->size];
}

在C++中，可以使用容器适配器priority_queue实现优先队列。

priority_queue可以支持的操作有：

q.empty()  队列为空返回值为真 ，

q.size() 返回队列元素个数，

q.pop() 删除最高优先级别的元素，

q.top()返回优先级别最高的元素，

q.push()以优先级插入元素

优先队列可以存放数组中的元素：

# include <iostream>
using namespace std;
# include <stdlib.h>
# include <functional>
# include <queue>
# include <vector>
int main()
{
	priority_queue<int,vector <int>,less<int> > q;  //把less<int> 换成 greater<int> 就可以建立最小优先队列
	int a[10]={1,2,3,4,5,6,7,8,9,10};
	int i=0;
	for(i=0;i<10;i++)
	q.push(a[i]);
	while(!q.empty())
	{
	cout<<q.top()<<endl;
	q.pop();
	}
	system("pause");
	return 0;
}

# include <iostream>
using namespace std;
# include <stdlib.h>
# include <functional>
# include <queue>
# include <vector>
class cmp{
int i;
public:
	cmp(int x):i(x){}
	friend bool operator <(const cmp &a,const cmp &b)   //建立最小优先队列
	{
	return a.i>b.i;
	}
	friend ostream& operator <<(ostream & os,const cmp t)
	{
		return os<<t.i<<endl;
	}
	int geti()
	{
	return i;
	}
};
int main()
{
	priority_queue <cmp> q;
	int i=0;
	for(i=0;i<10;i++)
	q.push(cmp(i));
	while(!q.empty())
	{
		cout<<q.top()<<endl;
		q.pop();
	}

	system("pause");
	return 0;
}

优先队列,布布扣,bubuko.com

优先队列

原文：http://blog.csdn.net/u011608357/article/details/22594201