上海最专业的网站设计制,东莞保安公司最新招聘,番禺网络,百度帐号登录一、什么是优先队列 优先队列是一个容器适配器#xff0c;存储于优先队列中的元素按照某种优先级自动排序。优先队列类似于堆#xff0c;元素可以随时插入#xff0c;但是只能弹出优先级最高的元素。默认是一个大根堆#xff0c;也就是元素越大#xff0c;优先级越高。
二…一、什么是优先队列 优先队列是一个容器适配器存储于优先队列中的元素按照某种优先级自动排序。优先队列类似于堆元素可以随时插入但是只能弹出优先级最高的元素。默认是一个大根堆也就是元素越大优先级越高。
二、优先队列的定义及初始化
2.1优先队列的定义
#include iostream
#include vector
#include queue
#include listusing namespace std;int main() {priority_queueint pq1;//创建一个默认的优先队列//默认是priority_queueint,vectorint,lessint() pq1;priority_queueint, vectorint, greaterint() pq2;//改为小根堆return 0;
}
2.2优先队列的初始化 优先队列没法像其他容器一样直接使用初始化列表进行初始化但它可以使用其它容器的迭代器进行初始化或者使用push函数与emplace函数依次输入函数。
#include iostream
#include vector
#include queue
#include listusing namespace std;int main() {vectorint v { 1,2,3,4,5,6,7 };priority_queueint pq1(v.begin(), v.end());while (!pq1.empty()){cout pq1.top() ;pq1.pop();}return 0;
}
三、list成员函数
3.1empty函数
bool empty() const; priority_queue提供了一个成员函数empty用于检查队列是否为空即检查其大小是否为零。这个函数实际上是调用了底层容器对象的empty成员函数。
#include iostream
#include vector
#include queue
#include listusing namespace std;int main() {vectorint v { 1,2,3,4,5,6,7 };listint l { 1,3,4,5,6,7 };priority_queueint pq1(l.begin(), l.end());priority_queueint pq2;cout pq1.empty() endl;cout pq2.empty() endl;return 0;
}
3.2size函数
size_type size() const; priority_queue提供了一个成员函数size用于返回优先队列中元素的数量。这个函数实际上是调用了底层容器对象的size成员函数。
#include iostream
#include vector
#include queue
#include listusing namespace std;int main() {vectorint v { 1,2,3,4,5,6,7 };listint l { 1,3,4,5,6,7 };priority_queueint pq1(l.begin(), l.end());priority_queueint pq2;cout pq1.size() endl;cout pq2.size() endl;return 0;
}
3.3top函数
const_reference top() const; priority_queue提供了一个成员函数top用于返回队头即优先级最高的元素。这个函数实际上是调用了底层容器对象的front成员函数。
#include iostream
#include vector
#include queue
#include listusing namespace std;int main() {vectorint v { 1,2,3,4,5,6,7 };listint l { 1,3,4,5,6,7 };priority_queueint pq1(l.begin(), l.end());priority_queueint pq2;cout pq1.top() endl;pq1.pop();cout pq1.top() endl;return 0;
}
3.4push函数
void push (const value_type val);
void push (value_type val); priority_queue提供了一个成员函数push用于向队列中插入一个新的元素。这个新元素的内容会被初始化为val指定的值。push函数首先调用底层容器对象的push_back成员函数来添加元素然后通过调用heap中的算法调整容器中所有元素的范围以确保新元素被放置在堆结构中正确的位置。
#include iostream
#include vector
#include queue
#include listusing namespace std;int main() {vectorint v { 1,2,3,4,5,6,7 };listint l { 1,3,4,5,6,7 };priority_queueint pq1(l.begin(), l.end());priority_queueint pq2;pq1.push(10);cout pq1.top() endl;pq1.pop();cout pq1.top() endl;return 0;
}
3.5emplace函数
template class... Args void emplace (Args... args); priority_queue提供了一个成员函数emplace它允许你在队列中就地构造一个新元素这意味着你可以直接传递给新元素构造函数的参数而不需要先创建一个临时对象再复制或移动到队列中。emplace函数首先调用底层容器的emplace_back成员函数来就地构造元素然后通过调用push_heap算法调整容器中所有元素的范围以确保新元素被放置在堆结构中正确的位置。
#include iostream
#include vector
#include queue
#include listusing namespace std;int main() {vectorint v { 1,2,3,4,5,6,7 };listint l { 1,3,4,5,6,7 };priority_queueint pq1(l.begin(), l.end());priority_queueint pq2;pq1.emplace(10);cout pq1.top() endl;pq1.pop();cout pq1.top() endl;return 0;
}
3.6pop函数
void pop(); priority_queue提供了一个成员函数pop用于移除队列顶部的元素也就是优先级最高的元素。这个操作会减少队列的大小一个单位。在调用pop之前可以使用top成员函数来检索即将被移除的元素的值。
#include iostream
#include vector
#include queue
#include listusing namespace std;int main() {vectorint v { 1,2,3,4,5,6,7 };listint l { 1,3,4,5,6,7 };priority_queueint pq1(l.begin(), l.end());priority_queueint pq2;cout pq1.top() endl;pq1.pop();cout pq1.top() endl;return 0;
}
3.7成员swap函数
void swap (priority_queue x) noexcept (/*see below*/); priority_queue提供了一个成员函数swap它用于交换两个priority_queue容器的元素。这个操作不仅交换了底层容器的内容还包括它们的比较函数。这个成员函数通过调用底层容器和比较函数的swap非成员函数来实现交换。
#include iostream
#include vector
#include queue
#include listusing namespace std;int main() {vectorint v { 1,2,3,4,5 };listint l { 5,6,7,8,9 };priority_queueint pq1(l.begin(), l.end());priority_queueint pq2(v.begin(), v.end());priority_queueint pq3(pq1);priority_queueint pq4(pq2);while (!pq1.empty()){cout pq1.top() ;pq1.pop();}cout endl;while (!pq2.empty()){cout pq2.top() ;pq2.pop();}cout endl;pq3.swap(pq4);while (!pq3.empty()){cout pq3.top() ;pq3.pop();}cout endl;while (!pq4.empty()){cout pq4.top() ;pq4.pop();}return 0;
} 四、非成员函数
4.1模板函数swap
template class T, class Container, class Compare
void swap (priority_queueT,Container,Compare x, priority_queueT,Container,Compare y) noexcept(noexcept(x.swap(y)));交换两个优先队列中元素时可以不适用成员swap函数转而使用算法标准库中的模板swap函数。
#include iostream
#include vector
#include queue
#include listusing namespace std;int main() {vectorint v { 1,2,3,4,5 };listint l { 5,6,7,8,9 };priority_queueint pq1(l.begin(), l.end());priority_queueint pq2(v.begin(), v.end());priority_queueint pq3(pq1);priority_queueint pq4(pq2);while (!pq1.empty()){cout pq1.top() ;pq1.pop();}cout endl;while (!pq2.empty()){cout pq2.top() ;pq2.pop();}cout endl;swap(pq3,pq4);while (!pq3.empty()){cout pq3.top() ;pq3.pop();}cout endl;while (!pq4.empty()){cout pq4.top() ;pq4.pop();}return 0;
}
