网站目录怎么做外链,网站服务器租用多少钱,网站建设找睿智骄阳,网站建设的素材文章目录 C 优先级队列用法与模拟实现介绍用法头文件1.创建优先级队列priority_queue 2. 插入元素push 3. 删除元素pop 访问顶部元素top 检查优先级队列的大小size 检查优先级队列是否为空empty 模拟实现 C 优先级队列用法与模拟实现
介绍
优先级队列#xff08;Priority Qu… 文章目录 C 优先级队列用法与模拟实现介绍用法头文件1.创建优先级队列priority_queue 2. 插入元素push 3. 删除元素pop 访问顶部元素top 检查优先级队列的大小size 检查优先级队列是否为空empty 模拟实现 C 优先级队列用法与模拟实现
介绍
优先级队列Priority Queue是一种抽象数据类型它类似于队列但是每个元素都有一个优先级或权重。在优先级队列中元素的出队顺序是按照优先级来进行的而不是先进先出FIFO或后进先出LIFO。 在 C 中优先级队列是通过 std::priority_queue 实现的它是 C 标准库的一部分。std::priority_queue 是一个模板容器适配器它提供常数时间复杂度的插入操作和 logarithmic 时间复杂度的删除操作。
用法
头文件
要使用 std::priority_queue你需要包含 queue 头文件。
#include queue1.创建优先级队列 priority_queue
(1) 构造函数可以接受两个参数一个比较函数和一个容器。是个显式构造不用隐式类型转换。(2) 接受两个迭代器的构造函数它允许你从一个范围 [first, last) 中的元素初始化优先级队列
//(1)
priority_queueint pq1; // 创建一个整数类型的优先级队列
priority_queueint, vectorint, lessint pq2;//创建一个以vector作为底层容器类型的优先级队列less是大堆
priority_queueint, vectorint, greaterint pq3; // 创建一个以vector作为底层容器类型的优先级队列greater是小堆//(2)
vectorint vec { 4, 1, 3, 2 };
priority_queueint pq(vec.begin(), vec.end());//pq 会用 vec 中的元素进行初始化并按照最大堆的顺序排列2. 插入元素 push
向优先级队列中插入元素。
pq.push(30);
pq.push(10);
pq.push(20);3. 删除元素 pop
从优先级队列中删除具有最高优先级的元素。
pq.pop(); // 删除元素 30访问顶部元素 top
访问优先级队列的顶部元素具有最高优先级的元素
int top pq.top(); // 之前在pop中把30pop了所以top现在是 20检查优先级队列的大小 size
查看优先级队列中的元素数量。
size_t size pq.size(); // size 现在是 2检查优先级队列是否为空 empty
检查优先级队列是否为空。
bool isEmpty pq.empty(); // isEmpty 现在是 false模拟实现 下面是一个简单的优先级队列的模拟实现使用数组和一个比较函数。
#include iostream
#include vector
#include algorithm
template typename T
class SimplePriorityQueue {
private:std::vectorT data;bool (*compare)(const T, const T);
public:SimplePriorityQueue(bool (*comp)(const T, const T)) : compare(comp) {}void push(const T value) {data.push_back(value);std::push_heap(data.begin(), data.end(), compare);}void pop() {std::pop_heap(data.begin(), data.end(), compare);data.pop_back();}T top() {return data.front();}bool empty() const {return data.empty();}size_t size() const {return data.size();}
};
bool compareInt(const int a, const int b) {return a b; // 大根堆
}
int main() {SimplePriorityQueueint pq(compareInt);pq.push(30);pq.push(10);pq.push(20);std::cout Top: pq.top() std::endl; // 输出 30pq.pop();std::cout Top: pq.top() std::endl; // 输出 20return 0;
}在这个模拟实现中我们使用了 std::vector 来存储数据并使用 std::push_heap 和 std::pop_heap 来维护堆的属性。我们还需要提供一个比较函数来定义元素的优先级。
