C++ priority_queue 优先队列

C++中优先队列的实现是利用堆来实现的。在STL库中的make_heap ， pop_heap以及push_heap来实现的。

主要的操作有：

1 push ： push进一个元素，并调整堆

2 pop : 弹出对首元素，并调整堆

3 size ： 返回队列中的元素个数

4 empty ： 队列是否为空

5 top ： 取出队首元素，但不删除该元素

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       using namespace std; template
      
       , class Compare = less
       
         > //采用类模板的形式，定义数组的元素类型以及底层实现的容器类型（此处为vector） //以及用于比较的函数对象 less。关于less greater，参见。。。 class my_priority_queue { private: Sequence c; //用于存放元素的vector Compare comp; //用于比较的函数对象 public: //类模板内部定义的类型 typedef typename Sequence::value_type value_type; typedef typename Sequence::size_type size_type; typedef typename Sequence::reference reference; typedef typename Sequence::const_reference const_reference; my_priority_queue():c(){} //如果没有指定比较函数，那么使用less template
        
          my_priority_queue(InputIterator beg, InputIterator end, const Compare &x = Compare()): c(beg, end),comp(x) { make_heap(c.begin(),c.end(), comp); } bool empty() const { return c.empty(); } size_type size() const { return c.size(); } const_reference top() const { return c.front(); } void pop() { if(empty()) { cout << "pop empty" << endl; exit(1); } pop_heap(c.begin(), c.end(), comp); c.pop_back(); } void push(const value_type &x) { c.push_back(x); push_heap(c.begin(), c.end(), comp); } }; int main() { my_priority_queue
         
           mpq; int A[] = {4,2,3,1}; my_priority_queue
          
            > mpq2(A, A+4); mpq2.push(5); cout << "mpq2.size() = " << mpq2.size() << endl; while(!mpq2.empty()) { cout << mpq2.top() << " "; mpq2.pop(); } if (mpq2.empty()) { cout << "mpq2 is empty..." << endl; } //使用greater比较函数， greater
           
            作为一个类型实例化类模板实参；greater
            
             () 作为函数对象！
            
           
          
         
        
       
      
     
    
   
  

	my_priority_queue
  
   , greater
   
     > mpq3(A, A+4, greater
    
     ()); mpq3.push(5); cout << "mpq3.size() = " << mpq3.size() << endl; while(!mpq3.empty()) { cout << mpq3.top() << " "; mpq3.pop(); } if(mpq3.empty()) { cout << "Empty.." << endl; } return 0; }