优先队列(priorityqueue)

队列是先进先出的线性表，顾名思义，优先队列则是元素有优先级的队列，出列的顺序由元素的优先级决定。从优先队列中删除元素是根据优先权的高低次序，而不是元素进入队列的次序。优先队列的典型应用是机器调度等。

假设我们对机器服务进行收费。每个用户每次使用机器所付费用都是相同的，但每个用户所需要服务时间都不同。为获得最大利润，假设只要有用户机器就不会空闲，我们可以把等待使用该机器的用户组织成一个最小优先队列，优先权即为用户所需服务时间。当一个新的用户需要使用机器时，将他 /她的请求加入优先队列。一旦机器可用，则为需要最少服务时间（即具有最高优先权）的用户提供服务。如果每个用户所需时间相同，但用户愿意支付的费用不同，则可以用支付费用作为优先权，一旦机器可用，所交费用最多的用户可最先得到服务，这时就要选择最大优先队列。

1.概念

优先队列（ priority queue）是0个或多个元素的集合，每个元素都有一个优先权或值，对优先队列执行的操作有 1) 查找； 2) 插入一个新元素； 3) 删除。在最小优先队列（ min priority q u e u e）中，查找操作用来搜索优先权最小的元素，删除操作用来删除该元素；对于最大优先队列（ max priority queue），查找操作用来搜索优先权最大的元素，删除操作用来删除该元素。优先权队列中的元素可以有相同的优先权，查找与删除操作可根据任意优先权进行。

描述优先队列最简单的方法是采用无序线性表。假设有一个具有n个元素的优先队列，如果采用公式化的线性表描述，那么插入操作可以十分方便的在表的右端末尾执行，插入操作的时间为O（1）。删除时必须查找优先权最大的元素，因此所需时间为O（n）。

若采用有序的线性表，则插入为O（n）,删除为O（1）

2.实现

由上面描述可以知道，我们可以在线性表的基础上完成优先队列，只需要改变删除的操作，当删除时找到最大或最小的值即可。

我们可以直接继承线性表类线性表的2种实现方式：数组和链表

线性表的公式化实现：

 #ifndef LINEARLIST_H

 #define LINEARLIST_H

 #include<iostream>

 #include<cstdlib>

 #include<new>

 using std::cout;

 using std::endl;

 template<class T>

 class LinearList

 {

     public:

         LinearList(int MaxListSize=);//构造函数

         virtual ~LinearList();

         bool IsEmpty()const

         {

             return length==;

         }

         int Length()const {return length;}

         bool Find(int k,T& x)const;//返回第K个元素到中

         int Search(T& x)const;//返回x的位置

         LinearList<T>& Delete(int k,T& x);//删除位置k的元素，并将元素值存到x

         LinearList<T>& Insert(int k,const T& x);//将x插入到k位置之后

         void Output(std::ostream& out)const;//输出到流

     protected:

         int length;//线性表当前长度

         int MaxSize;//最大长度

         T *element;//线性表数组

 };

 class NoMem

 {

     public :

     NoMem(){

         cout<<"No Memory"<<endl;

     //std::exit(1);

     }

 };

 class OutofBounds

 {

 public :

     OutofBounds()

     {

         cout<<"Out of Bounds"<<endl;

     //std::exit(1);

     }

 };

 void my_new_handler()

 {

     throw NoMem();

 }

 template<class T>

 LinearList<T>::LinearList(int MaxListSize)

 {

     std::new_handler old_Handler=std::set_new_handler(my_new_handler);

     MaxSize=MaxListSize;

     element=new T[MaxSize];

     length=;

 }

 template<class T>

 LinearList<T>::~LinearList()

 {

     delete[]element;

     MaxSize=;

     length=;

 }

 template<class T>

 bool LinearList<T>::Find(int k,T&x)const

 {

     if(k<||k>length)

         return false;

      x=element[k-];

      return true;

 }

 template<class T>

 int LinearList<T>::Search(T &x)const

 {

     int i=;

     while(i<length&&element[i]!=x)

     {

         i++;

     }

     if(i==length) return ;

     else return i+;

 }

 template<class T>

 LinearList<T>& LinearList<T>::Delete(int k,T &x)

 {

     if(Find(k,x))//存在位置k

     {

         for(int i=k;i<length;++i)

         {

             element[i-]=element[i];//k之后元素向前移动一位

         }

         length--;

         return *this;

     }

     else

     {

        throw OutofBounds();

     }

 }

 template<class T>

 LinearList<T>& LinearList<T>::Insert(int k,const T &x)

 {

     if(k<||k>length)

     {

        throw OutofBounds();

     }

     else if(length==MaxSize)

     {

         throw NoMem();

     }

     else

         {

             for(int i=length;i>k;--i)

             {

                 element[i]=element[i-];//k之后元素向后移动一位

             }

             element[k]=x;

             length++;

             return *this;

         }

 }

 template<class T>

 void LinearList<T>::Output(std::ostream& out)const

 {

     for(int i=;i<length;i++)

     {

         out<<element[i]<<" ";

     }

 }

 template<class T>

 std::ostream& operator<<(std::ostream &out,const LinearList<T>& x)

 {

     x.Output(out);

     return out;

 }

 #endif // LINEARLIST_H

最大优先队列：

 #ifndef PRIORITYQUEUE_H

 #define PRIORITYQUEUE_H

 #include "LinearList.h"

 template<typename T>

 class PriorityQueue:public LinearList<T>

 {

 public:

     PriorityQueue(int MaxListSize=):LinearList<T>::LinearList(MaxListSize){};

     PriorityQueue<T>& Insert(const T& x);

     PriorityQueue<T>& Delete(T& x);

     T Max() const;

     ~PriorityQueue(){};

     //void Output(std::ostream& out)const;//输出到流

     friend ostream& operator<< <>(ostream& output, const PriorityQueue<T>& x);

 private:

     size_t MaxIndex() const;

 };

 //末端插入

 template<typename T>

 PriorityQueue<T>& PriorityQueue<T>::Insert(const T& x)

 {

     if (length>=MaxSize)

     {

         throw NoMem();

     }

     element[length++] = x;

     return *this;

 }

 //找到最大值的索引（下标）

 template<typename T>

 size_t PriorityQueue<T>::MaxIndex() const

 {

     if (length == )

     {

         throw OutofBounds();

     }

     size_t maxNum = ;

     for (size_t i = ; i < length; ++i)

     {

         if (element[i]>element[maxNum])

         {

             maxNum = i;

         }

     }

     return maxNum;

 }

 //返回最大值

 template<typename T>

 T PriorityQueue<T>::Max() const

 {

     if (length==)

     {

         throw OutofBounds();

     }

     size_t maxNum = MaxIndex();

     return element[maxNum];

 }

 //取出最大值

 template<typename T>

 PriorityQueue<T>& PriorityQueue<T>::Delete(T& x)

 {

     if (length==)

     {

         throw OutofBounds();

     }

     size_t maxindex = MaxIndex();

     x = element[maxindex];

     //元素前移

     for (size_t i = maxindex; i < length-;++i)

     {

         element[i] = element[i + ];

     }

     --length;

     return *this;

 }

 /*

 template<typename T>

 void PriorityQueue<T>::Output(std::ostream& out) const

 {

     if (length==0)

     {

         throw OutofBounds();

     }

     for (size_t i = 0; i < length;++i)

     {

         out << element[i]<<' ';

     }

     out << endl;

 }

 */

 template<typename T>

 ostream& operator<<(ostream& output,const PriorityQueue<T>& x)

 {

     x.Output(output);

     return output;

 }

 #endif

测试：

 #include<iostream>

 using namespace std;

 #include "PriorityQueue.h"

 int main()

 {

     PriorityQueue<int> testQ;

     testQ.Insert();

     testQ.Insert();

     testQ.Insert();

     testQ.Insert();

     cout << "Queue is: " << endl;

     cout << testQ << endl;

     cout << "Queue size is: " << testQ.Length();

     cout << endl;

     cout << "Max in Queue is: " << testQ.Max();

     cout << endl;

     int x;

     testQ.Delete(x);

     cout << "element deleted is: " << x<<endl;

     cout << "Queue is: " << endl;

     cout << testQ << endl;

     cout << "Queue size is: " << testQ.Length();

     cout << endl;

     cout << "Max in Queue is: " << testQ.Max();

     cout << endl;

     return ;

 }

巴特西

优先队列(priorityqueue)

最新文章

热门文章