文档章节

priority_queue优先队列/C++

Frank-yang
 Frank-yang
发布于 2017/09/04 11:22
字数 592
阅读 14
收藏 0

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/

© 著作权归作者所有

共有 人打赏支持
Frank-yang
粉丝 0
博文 29
码字总数 55893
作品 0
广州
UVA ~ 11995 ~ I Can Guess the Data Structure! (模拟)

题意:你有一个类似“包包”的数据结构,支持两种操作,如表3-1所示。 □1 x,把元素x放进包包 □2 从包包中拿出一个元素 给出一系列操作以及返回值,你的任务是猜猜这个“包包”到底是什么。...

zscdst
05/02
0
0
iOS多线程编程之Grand Central Dispatch(GCD)介绍和使用

介绍: Grand Central Dispatch 简称(GCD)是苹果公司开发的技术,以优化的应用程序支持多核心处理器和其他的对称多处理系统的系统。这建立在任务并行执行的线程池模式的基础上的。它首次发...

木木情深
2014/02/19
0
0
iOS多线程编程之Grand Central Dispatch(GCD)介绍和使用

iOS多线程编程之Grand Central Dispatch(GCD)介绍和使用 目录(?)[+] 介绍: Grand Central Dispatch 简称(GCD)是苹果公司开发的技术,以优化的应用程序支持多核心处理器和其他的对称多处理...

malawo
2013/09/05
0
0
初学图论-Dijkstra单源最短路径算法基于优先级队列(Priority Queue)的实现

这一次,笔者使用了STL库中的优先级队列(Priority Queue)来完成Dijkstra算法中extract-min()语句(即从未选中的节点中选取一个距离原点s最小的点)的功能。由于优先级队列的插入、删除操作只...

不高不富不帅的陈政_
2015/08/07
0
0
完整详解GCD系列(一)dispatch_async;dispatch_sync;dispatch_

为什么要写这个系列,因为百度了一下,找了很多都是些片面的Blog,拷贝来拷贝去的,写的也很粗糙。 所以,我要写这个系列,尽量把官网文档中GCD的强大功能完整的表达出来。方便自己,也方便别...

hejunbinlan
2015/07/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

[雪峰磁针石博客]python3快速入门教程1 turtle绘图-2函数

菲波那契序列: >>> # Fibonacci series:... # the sum of two elements defines the next... a, b = 0, 1>>> while b < 10:... print(b)... a, b = b, a+b...112......

python测试开发人工智能安全
今天
0
0
java环境变量配置最正确的方式

原贴:https://blog.csdn.net/qq_40007997/article/details/79784711,十分详细,亲测有效

kitty1116
今天
0
0
49.Nginx防盗链 访问控制 解析php相关 代理服务器

12.13 Nginx防盗链 12.14 Nginx访问控制 12.15 Nginx解析php相关配置(502的问题) 12.16 Nginx代理 扩展 502问题汇总 http://ask.apelearn.com/question/9109 location优先级 http://blog....

王鑫linux
今天
1
0
Nginx防盗链、访问控制、解析php相关配置、Nginx代理

一、Nginx防盗链 1. 编辑虚拟主机配置文件 vim /usr/local/nginx/conf/vhost/test.com.conf 2. 在配置文件中添加如下的内容 { expires 7d; valid_referers none blocked server_names *.tes......

芬野de博客
今天
0
0
spring EL 和资源调用

资源调用 import org.springframework.beans.factory.annotation.Value;import org.springframework.context.annotation.PropertySource;import org.springframework.core.io.Resource;......

Canaan_
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部