优先级队列

PQueue.h

#ifndef PQUEUE_H
#define PQUEUE_H

#include<assert.h>
#include<iostream>
#include<stdlib.h>
using namespace std;
const int DefaultPQSize=50;

template<typename T>
class PQueue{
public:
    PQueue(int sz=DefaultPQSize);
    ~PQueue(){
        delete[] pqelements;
    }
    bool Insert(const T& x);
    bool RemoveMin(T& x);
    bool getFront(T& x)const;
    void makeEmpty(){count=0;}
    bool IsEmpty()const{
        return count==0?true:false;
    }
    bool IsFull()const{
        return count==maxSize?true:false;
    }
    int getSize()const{
        return count;
    }
    friend ostream& operator<<(ostream& os,PQueue& pq){
        for(int i=0;i<pq.count;i++){
            os << pq.pqelements[i] << " ";
        }
        os << endl;
        return os;
    }

protected:
    T * pqelements;
    int count;//当前元素个数
    int maxSize;
    void adjust();
};

template<typename T>
PQueue<T>::PQueue(int sz):count(0),maxSize(maxSize)
{
    pqelements = new T[sz];
    assert(NULL!=pqelements);
}

template<typename T>
bool PQueue<T>::Insert(const T &x)
{
    if(IsFull()){
        return false;
    }
    pqelements[count++]=x;
    adjust();
}

/*
  将最新插入的结点放到合适的位置，相当于排序
  */
template<typename T>
void PQueue<T>::adjust()
{
    T last = pqelements[count-1];
    int j;
    for(j=count-2;j>0;j--){
        if(pqelements[j]<=last){
            break;
        }else{
            pqelements[j+1] = pqelements[j];
        }
    }
    pqelements[j+1]=last;
}

template<typename T>
bool PQueue<T>::RemoveMin(T &x)
{
    if(IsEmpty()){
        return false;
    }else{
        for(int i=1;i<count;i++){
            pqelements[i-1] = pqelements[i];
        }
    }
    count--;
    return true;
}

template<typename T>
bool PQueue<T>::getFront(T &x) const
{
    if(IsEmpty()){
        return false;
    }
    x = pqelements[0];
    return true;
}

#endif // PQUEUE_H

PQueue.cpp

#include"PQueue.h"

int main()
{
    PQueue<int> pq;
    int num=1;
    for(int i=0;i<10;++i){
        pq.Insert(num++);
    }
    cout << pq;
    pq.RemoveMin(num);
    cout << pq;
    pq.makeEmpty();
    cout << pq;
}

1 2 3 4 5 6 7 8 9 10 
2 3 4 5 6 7 8 9 10