小编给大家分享一下C++中priority_queue如何实现,相信大部分人都还不怎么了解,因此分享这篇文章给大家参考一下,希望大家阅读完这篇文章后大有收获,下面让我们一起去了解一下吧!
优先级队列是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素。
优先队列是一种容器适配器,首先要包含头文件 #include<queue>, 他和queue不同的就在于我们可以自定义其中数据的优先级, 让优先级高的排在队列前面,优先出队。
优先级队列默认使用vector作为其底层存储数据的容器,在vector上又使用了堆算法将vector中元素构造成堆的结构,因此priority_queue就是堆,所有需要用到堆的位置,都可以考虑使用priority_queue。
注意:默认情况下priority_queue是大根堆。如果想让其生成小根堆,需要使用到仿函数或者Lambda表达式。
由于priority_queue是一种容器适配器,适配的是vector,我们在vector中已经写过它的构造函数了。故priority_queue在此不需要多余的其他构造函数。
// 创造空的优先级队列 priority_queue():m_priority_queue() { } template<class Iterator> priority_queue(Iterator first, Iterator last) : m_priority_queue(first, last) { // 将m_priority_queue中的元素调整成堆的结构 int count = m_priority_queue.size(); int root = ((count - 2) >> 1); for (; root >= 0; root--) AdjustDown(root); }
功能:push函数用来往堆中(尾部)插入一个元素,并向上调整成新的堆。
//向上调整 void AdjustUp(int child) { int parent = (child-1)>>1; while (child > 0) { //其中c是一个对象,用该对象去调用仿函数来进行比较 if (c(m_priority_queue[parent], m_priority_queue[child])) { std::swap(m_priority_queue[parent], m_priority_queue[child]); child = parent; parent = (child - 1) >> 1; } else { break; } } } void push(const T& val) { m_priority_queue.push_back(val); AdjustUp(m_priority_queue.size()-1); }
功能:pop函数弹出堆顶元素。具体步骤是:堆顶元素与最后一个数字进行交换位置。之后在进行尾删来删除堆顶。再重新向下调堆。
//向下调堆 void AdjustDown(int parent) { int child = (parent << 1) + 1; int size = static_cast<int>(m_priority_queue.size()); while (child< size) { if (child + 1 < size && c(m_priority_queue[child],m_priority_queue[child + 1]) ) { ++child; } if (c(m_priority_queue[parent], m_priority_queue[child])) { std::swap(m_priority_queue[parent], m_priority_queue[child]); parent = child; child = (parent << 1) + 1; } else { break; } } } void pop() { assert(!m_priority_queue.empty()); std::swap(m_priority_queue[0], m_priority_queue[m_priority_queue.size()- 1]); m_priority_queue.pop_back(); AdjustDown(0); }
功能:用来获取堆中的元素个数。
size_t size() const { return m_priority_queue.size(); }
功能:用来判断堆中是否为空。
bool empty() const { return m_priority_queue.empty(); }
功能:用来获取堆顶的元素。
T& top() { return m_priority_queue.front(); } const T& top() const { return m_priority_queue.front(); }
代码实现
#pragma once #define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> #include<vector> #include<assert.h> namespace ZJ { template<class T> class less { public: bool operator() (const T& x, const T& y) const { return x < y; } }; template<class T> class greater { public: bool operator() (const T& x, const T& y) const { return x > y; } }; template<class T,class Container=std::vector<T>, class Compare = ZJ::less<T>> class priority_queue { public: // 创造空的优先级队列 priority_queue():m_priority_queue() { } template<class Iterator> priority_queue(Iterator first, Iterator last) : m_priority_queue(first, last) { // 将m_priority_queue中的元素调整成堆的结构 int count = m_priority_queue.size(); int root = ((count - 2) >> 1); for (; root >= 0; root--) AdjustDown(root); } public: //向上调整 void AdjustUp(int child) { int parent = (child-1)>>1; while (child > 0) { if (c(m_priority_queue[parent], m_priority_queue[child])) { std::swap(m_priority_queue[parent], m_priority_queue[child]); child = parent; parent = (child - 1) >> 1; } else { break; } } } void push(const T& val) { m_priority_queue.push_back(val); AdjustUp(m_priority_queue.size()-1); } void AdjustDown(int parent) { int child = (parent << 1) + 1; int size = static_cast<int>(m_priority_queue.size()); while (child< size) { if (child + 1 < size && c(m_priority_queue[child],m_priority_queue[child + 1]) ) { ++child; } if (c(m_priority_queue[parent], m_priority_queue[child])) { std::swap(m_priority_queue[parent], m_priority_queue[child]); parent = child; child = (parent << 1) + 1; } else { break; } } } void pop() { assert(!m_priority_queue.empty()); std::swap(m_priority_queue[0], m_priority_queue[m_priority_queue.size()- 1]); m_priority_queue.pop_back(); AdjustDown(0); } size_t size() const { return m_priority_queue.size(); } T& top() { return m_priority_queue.front(); } const T& top() const { return m_priority_queue.front(); } bool empty() const { return m_priority_queue.empty(); } private: Container m_priority_queue; Compare c; }; }
以上是“C++中priority_queue如何实现”这篇文章的所有内容,感谢各位的阅读!相信大家都有了一定的了解,希望分享的内容对大家有所帮助,如果还想学习更多知识,欢迎关注亿速云行业资讯频道!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。