优先队列

　　原始的队列遵循先进先出，队列尾入队列，队头出队列。而优先队列出队列的是优先级最高的那个元素（该优先级次序自己设定），而入队时自动按该优先级顺序插入（插入后调整）。

　　注意：优先队列利用到堆排序的知识，最好先学堆排序。。。额，没学也没多大事。。。。。

下面给出我用c++写的优先队列的各功能实现。。。

  1 #include<stdio.h>
  2 #include<string>
  3 #include<iostream>
  4 using namespace std;
  5 #define Max 10000
  6 //队列元素自己设定
  7 typedef struct node
  8 {
  9   int key;
 10   //下面就是优先顺序的设定
 11   bool friend operator < (const node &a,const node &b)
 12   {
 13     return a.key < b.key;
 14   }
 15 }Node;
 16 //优先队列各项功能实现
 17 class PQueue
 18 {
 19   private:
 20     Node v[Max];
 21     int length;
 22     void heap_adjust(int l,int r)    //堆排序的核心（调整）
 23     {
 24       int j=l<<1;
 25       Node tmp=v[l];
 26       while(j<=r)
 27       {
 28         if(j<r&&v[j]<v[j+1]) j++;
 29         if(tmp<v[j]) v[l]=v[j];
 30         else break;
 31         l=j;
 32         j<<=1;
 33       }
 34       v[l]=tmp;
 35     }
 36   public:
 37     PQueue()
 38     {
 39       length=0;
 40     }
 41     //堆排序部分
 42     void creat_heap()
 43     {
 44       for(int i=length>>1;i>0;i--)
 45         heap_adjust(i,length);
 46     }
 47     void set_size(int len)
 48     {
 49       length=len;
 50     }
 51 //如果不用下面的两个函数进行直接赋值或排序，就不需要特地调用creat_heap()函数
 52     void set_value(int i,Node value)
 53     {
 54       v[i]=value;
 55     }
 56     void heap_sort()
 57     {
 58       for(int i=length;i>1;i--)
 59       {
 60         Node tmp=v[i];
 61         v[i]=v[1];
 62         v[1]=tmp;
 63         heap_adjust(1,i-1);
 64       }
 65     }
 66     bool Is_heap()
 67     {
 68       int j;
 69       if(length<=1) return true;
 70       for(int i=length>>1;i>0;i--)
 71       {
 72         j=i<<1;
 73         if(j<length&&v[j]<v[j+1]) j++;
 74         if(v[i]<v[j]) return false;
 75       }
 76       return true;
 77     }
 78     //重头戏，优先队列的入队列和出队列
 79     bool Is_empty()
 80     {
 81       return length==0;
 82     }
 83     bool Is_full()
 84     {
 85       return length==Max-1;
 86     }
 87     bool push(Node value)
 88     {
 89       if(Is_full()) return false;
 90       v[++length]=value;
 91       int i=length;
 92       int j=length>>1;
 93       while(j>0)
 94       {
 95         if(!(v[j]<v[i])) break;
 96         Node tmp=v[i];
 97         v[i]=v[j];
 98         v[j]=tmp;
 99         i=j;
100         j>>=1;
101       }
102       return true;
103     }
104     bool pop()
105     {
106       if(Is_empty()) return false;
107       Node tmp=v[1];
108       v[1]=v[length];
109       v[length]=tmp;
110       length--;
111       heap_adjust(1,length);
112       return true;
113     }
114     bool pop(Node &value)
115     {
116       if(Is_empty()) return false;
117       Node tmp=v[1];
118       v[1]=v[length];
119       v[length]=tmp;
120       value=v[length];
121       length--;
122       heap_adjust(1,length);
123       return true;
124     }
125     bool top(Node &value)
126     {
127       if(Is_empty()) return false;
128       value=v[1];
129       return true;
130     }
131     int size()
132     {
133       return length;
134     }
135 };
136 int main()
137 {
138 
139   return 0;
140 }

View Code

　　下面给出一道优先队列的基础题：

　 http://codeforces.com/contest/129/problem/D

　　这道题的解题用到优先队列，而且是最基本的暴力。

　　在c++中，有priority_queue，可以直接用它定义一个优先队列，用法先写一个想要的队列元素的数据结构（也可以是int等基本数据类型），定义好优先级别，就可以使用了: priority_queue<Node> a;

　具体用法百度吧。。。