C++ 优先队列用法

最近用近似算法实现旅行商问题，需要首先求解最小生成树，用Prim算法求解最小生成树，需要找割的最小边。于是想到了使用priority_queue，现在把priority_queue用法总结一下，不废话了，总结完了，快点求解TSP。

在STL中它的源码如下：

class priority_queue

{

     protected:
         _Sequence  c;                  ///容器
        _Compare   comp;          ///比较准则
     public:
     bool empty() const
     { return c.empty(); }
     size_type size() const
     { return c.size(); }
     const_reference top() const
     {
         __glibcxx_requires_nonempty();
         return c.front();
     }
     void push(const value_type& __x)
     {
         try
         {
          c.push_back(__x);
          std::push_heap(c.begin(), c.end(), comp);
        }
        catch(...)
        {
           c.clear();
           __throw_exception_again;
         }
     }
     void pop()
     {
         __glibcxx_requires_nonempty();
         try
         {
           std::pop_heap(c.begin(), c.end(), comp);
           c.pop_back();
         }
         catch(...)
         {
           c.clear();
           __throw_exception_again;
         }
     }

}

用法：

C++头文件 #include <queue>

template<typename _Tp,
             typename _Sequence = vector<_Tp>,
             typename _Compare  = less<typename _Sequence::value_type> >

第一个参数 _Tp： 指定存储的类型名称；

第二个参数 _Sequence： 指定存储的数据结构，该结果必须支持随机存取迭代器；

第三个参数 _Compare ： 比较函数，对于自定义类型有两种方法实现大小顶堆，第一个是重载操作符，第二个是写一个结构实现比较。

各个数据类型算法讲解如下：

1.  对于一般的基本数据类型，比如 int，double等。

1).    默认是大顶堆，测试代码如下

   

其中省略了比较泛型函数less<int> (上面那个greater<int>是写错了。应该是less<int>,或者省略。)

输出结果如下：

2).   小顶堆实现如下：

其中加上了存储的数据结构，和比较函数大小。

输出结果如下：

2.  对于自定义类型，必须实现比较函数。

自定义类型如下：

实现小顶堆：

自定义比较函数，这里选择实现比较结构：

测试代码为：

运行结果如下：

等价的重载大于号实现：

测试代码：

运行结果：

总结大顶堆于小于号有关，小顶堆与大于号有关，这样关联起来就不会忘了。