首页 > 代码库 > priority_queue的简单实现
priority_queue的简单实现
优先级队列相对于普通队列，提供了插队功能，每次最先出队的不是最先入队的元素，而是优先级最高的元素。
它的实现采用了标准库提供的heap算法。该系列算法一共提供了四个函数。使用方式如下：
首先建立一个容器，放入元素:
1 vector<int> vec;2 insertNums(vec, 3, 7);3 insertNums(vec, 5, 9);4 insertNums(vec, 1, 4);
打印结果为:
all elements3 4 5 6 7 5 6 7 8 9 1 2 3 4
然后调用make_heap()， 将容器内[begin(), end())的元素建立成堆:
make_heap(vec.begin(), vec.end());
打印结果为:
after make heap9 8 6 7 7 5 5 3 6 4 1 2 3 4
然后我们调用pop_heap(),该算法必须保证[begin(),end())之间的元素已经是一个堆，
然后它将堆顶的元素放到最后，再将[begin(),end() - 1)内的元素重新排列成堆:
pop_heap(vec.begin(), vec.end());vec.pop_back();print(vec, "after pop heap");
打印结果为:
after pop heap8 7 6 7 4 5 5 3 6 4 1 2 3
接下来调用push_heap(),该算法必须保证[begin(),end() - 1)已经是一个堆，再将整个[begin(),end())调整为一个堆:
vec.push_back(17);push_heap(vec.begin(), vec.end());print(vec, "after push heap");
打印结果为:
after push heap17 7 8 7 4 5 6 3 6 4 1 2 3 5
最后我们调用sort_heap(),将[begin(),end())中的元素转化为有序序列，前提是[begin(),end())已经是一个堆:
sort_heap(vec.begin(), vec.end());print(vec, "after sort heap");
打印结果为:
after sort heap1 2 3 3 4 4 5 5 6 6 7 7 8 17
完整的测试代码为:
#include <iostream>#include <string>#include <vector>#include <algorithm>using namespace std;template <typename T>void insertNums(T &t, int first, int last){ while(first <= last) { t.insert(t.end(), first); ++ first; }}template <typename T>void print(const T &t, const std::string &s = ""){ cout << s << endl; for(typename T::const_iterator it = t.begin(); it != t.end(); ++ it) cout << *it << " "; cout << endl;}int main(int argc, char const *argv[]){ vector<int> vec; insertNums(vec, 3, 7); insertNums(vec, 5, 9); insertNums(vec, 1, 4); print(vec, "all elements"); make_heap(vec.begin(), vec.end()); print(vec, "after make heap"); pop_heap(vec.begin(), vec.end()); vec.pop_back(); print(vec, "after pop heap"); vec.push_back(17); push_heap(vec.begin(), vec.end()); print(vec, "after push heap"); sort_heap(vec.begin(), vec.end()); print(vec, "after sort heap"); return 0;}
根据以上算法，我们来实现优先级队列priority_queue，代码如下:
1 #ifndef PRIORITY_QUEUE_H 2 #define PRIORITY_QUEUE_H 3 #include <vector> 4 #include <algorithm> 5 #include <functional> 6 7 template <typename T, 8 typename Container = std::vector<T>, 9 typename Compare = std::less<typename Container::value_type> >10 class PriorityQueue11 {12 public:13 typedef typename Container::value_type value_type;14 typedef typename Container::size_type size_type;15 typedef Container container_type;16 typedef value_type& reference;17 typedef const value_type& const_reference;18 19 PriorityQueue(const Compare &comp = Compare(),20 const Container &cont = Container());21 22 23 24 template <typename InputIter>25 PriorityQueue(InputIter first, InputIter last,26 const Compare &comp = Compare(),27 const Container &cont = Container());28 29 void push(const value_type &val)30 {31 _cont.push_back(val);32 std::push_heap(_cont.begin(), _cont.end(), _comp);33 }34 35 void pop()36 {37 std::pop_heap(_cont.begin(), _cont.end(), _comp);38 _cont.pop_back();39 }40 41 bool empty() const { return _cont.empty(); }42 size_type size() const { return _cont.size(); }43 44 const_reference top() const { return _cont.front(); }45 46 private:47 Compare _comp;48 Container _cont;49 50 };51 52 template <typename T, typename Container, typename Compare>53 PriorityQueue<T, Container, Compare>::PriorityQueue(const Compare &comp,54 const Container &cont)55 :_comp(comp), _cont(cont)56 {57 std::make_heap(_cont.begin(), _cont.end(), _comp);58 }59 60 61 template <typename T, typename Container, typename Compare>62 template <typename InputIter>63 PriorityQueue<T, Container, Compare>::PriorityQueue(InputIter first, InputIter last,64 const Compare &comp,65 const Container &cont)66 :_comp(comp), _cont(cont)67 {68 _cont.insert(_cont.end(), first, last);69 std::make_heap(_cont.begin(), _cont.end(), _comp);70 }71 72 #endif
测试代码如下:
1 #include "priority_queue.hpp" 2 #include <iostream> 3 using namespace std; 4 5 int main(int argc, const char *argv[]) 6 { 7 PriorityQueue<float> q; 8 q.push(66.6); 9 q.push(22.3);10 q.push(44.4);11 12 cout << q.top() << endl;13 q.pop();14 cout << q.top() << endl;15 q.pop();16 q.push(11.1);17 q.push(55.5);18 q.push(33.3);19 q.pop();20 21 while(!q.empty())22 {23 cout << q.top() << " ";24 q.pop();25 }26 cout << endl;27 28 29 30 return 0;31 }
测试结果为:
66.644.433.3 22.3 11.1
priority_queue的简单实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。