priority_queue优先队列/C++
priority_queue优先队列/C++
Frank-yang 发表于3个月前
priority_queue优先队列/C++
  • 发表于 3个月前
  • 阅读 5
  • 收藏 0
  • 点赞 0
  • 评论 0

腾讯云 新注册用户 域名抢购1元起>>>   

priority_queue优先队列/C++

概述

  priority_queue是一个拥有权值观念的queue,只允许在底端加入元素,并从顶端取出元素。
  priority_queue带有权值观念,权值最高者,排在最前面。
  缺省情况下priority_queue系利用一个max-heap完成,后者是一个以vector表现的complete binary tree。

定义

  由于priority_queue完全以底部容器为根据,再加上heap处理规则,所以其实现非常简单。缺省情况下是以vector为底部容器。
  priority_queue的所有元素,进出都有一定的规则,只有queue顶端的元素(权值最高者),才有机会被外界取用。priority_queue不提供遍历功能,也不提供迭代器。
  底部用到了:make_heap,push_heap,pop_heap(三个都是泛型算法)

push_heap: 先利用底层容器的push_back()将新元素推入末尾,再重排heap。
pop_heap: 从heap内取出一个元素。它并不是真正将元素弹出,而是重排heap,然后再以底层容器的pop_back()取得被弹出的元素。

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;
  • T - The type of the stored elements. The behavior is undefined if T is not the same type as Container::value_type. (since C++17)
  • Container - The type of the underlying container to use to store the elements. The container must satisfy the requirements of SequenceContainer, and its iterators must satisfy the requirements of RandomAccessIterator. Additionally, it must provide the following functions with the usual semantics:
    front()
    push_back()
    pop_back()
      The standard containers std::vector and std::deque satisfy these requirements.
      //底层只能是vector 和 deque 实现
  • Compare - A Compare type providing a strict weak ordering.
      std::greater 可以使最小元素出现在队首(内部是最小堆)

操作

常用函数 作用
top 取队头元素
empty 判断优先队列是否为空
size 优先队列中元素个数
push 向优先队列中添加一个元素
pop 弹出队头元素(返回值是void)

example

#include <functional>
#include <queue>
#include <vector>
#include <iostream>
 
template<typename T> void print_queue(T& q) {
    while(!q.empty()) {
        std::cout << q.top() << " ";
        q.pop();
    }
    std::cout << '\n';
}
 
int main() {
    std::priority_queue<int> q;
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q.push(n);
 
    print_queue(q);
 
    std::priority_queue<int, std::vector<int>, std::greater<int> > q2;
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q2.push(n);
 
    print_queue(q2);
 
    // Using lambda to compare elements.
    auto cmp = [](int left, int right) { return (left ^ 1) < (right ^ 1);};
    std::priority_queue<int, std::vector<int>, decltype(cmp)> q3(cmp);
 
    for(int n : {1,8,5,6,3,4,0,9,7,2})
        q3.push(n);
 
    print_queue(q3); 
}

output:
9 8 7 6 5 4 3 2 1 0
0 1 2 3 4 5 6 7 8 9
8 9 6 7 4 5 2 3 0 1

http://www.frankyang.cn/2017/08/31/priorityqueue/

共有 人打赏支持
粉丝 0
博文 27
码字总数 54518
×
Frank-yang
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: