文档章节

priority_queue优先队列/C++

Frank-yang
 Frank-yang
发布于 2017/09/04 11:22
字数 592
阅读 10
收藏 0
点赞 0
评论 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

C语言编程学习:线性结构的两种常见应用之二:队列

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 05/17 ⋅ 0

C++ STL学习——queue

我们在上一篇博客中《C++ STL学习——stack》简单介绍了STL 中stack这种数据结构的使用,这篇博客主要来讲一下queue队列的使用。其实queue的使用和stack一样简单。示例代码上传至 https://gi...

chenyufeng1991 ⋅ 2016/08/23 ⋅ 0

C++ STL学习——deque

在数据结构中还有一种很常见的队列叫做双端队列,我们在上一篇博客《C++ STL学习——queue》中讲到的队列queue是一种最标准的队列,只能在尾部插入数据,在头部删除数据。而今天我们讲到的d...

chenyufeng1991 ⋅ 2016/09/07 ⋅ 0

C语言编程基础学习——队列详细讲解!

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 03/20 ⋅ 0

精选的这19道C/C+面试题,你能答对多少呢?

软件工程师的面试,套路都差不多,这一次约到的问题,下次你可能还会遇到。 问1:请用简单的语言告诉我C++ 是什么? 答:C++是在C语言的基础上开发的一种面向对象编程语言,应用广泛。C++支持...

悟空_b201 ⋅ 06/02 ⋅ 0

C语言编程基础入门学习数据结构中队列的实现与操作

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 03/15 ⋅ 0

C语言/C++对编程学习的重要性!

C语言是面向过程的,而C++是面向对象的 C和C++的区别: C是一个结构化语言,它的重点在于算法和数据结构。C程序的设计首要考虑的是如何通过一个过程,对输入(或环境条件)进行运算处理得到...

小辰带你看世界 ⋅ 06/02 ⋅ 0

面试常考的常用数据结构与算法【简】

数据结构与算法,这个部分的内容其实是十分的庞大,要想都覆盖到不太容易。在校学习阶段我们可能需要对每种结构,每种算法都学习,但是找工作笔试或者面试的时候,要在很短的时间内考察一个人...

anlve ⋅ 05/01 ⋅ 0

最新名企招聘现场,现场实拍笔试部分

大企面试现场,最新笔试题分享,小编也不断收到网友们投稿(现场笔试实拍) 持续关注:iOS首席鉴黄师,持续输出各大公司iOS面试系列文章,欢迎广大程序猿找我投稿面试中碰到的面试题,我会给...

iOS首席鉴黄师 ⋅ 06/04 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

OSChina 周三乱弹 —— 这样的女人私生活太混乱了

Osc乱弹歌单(2018)请戳(这里) 【今日歌曲】 @ 胖达panda :你经历过体验到人生的大起大落吗?我一朋友在10秒内体验了,哈哈。@小小编辑 请点一首《almost lover》送给他。 《almost love...

小小编辑 ⋅ 44分钟前 ⋅ 7

自己动手写一个单链表

文章有不当之处,欢迎指正,如果喜欢微信阅读,你也可以关注我的微信公众号:好好学java,获取优质学习资源。 一、概述 单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对...

公众号_好好学java ⋅ 49分钟前 ⋅ 0

Centos7重置Mysql 8.0.1 root 密码

问题产生背景: 安装完 最新版的 mysql8.0.1后忘记了密码,向重置root密码;找了网上好多资料都不尽相同,根据自己的问题总结如下: 第一步:修改配置文件免密码登录mysql vim /etc/my.cnf 1...

豆花饭烧土豆 ⋅ 今天 ⋅ 0

熊掌号收录比例对于网站原创数据排名的影响[图]

从去年下半年开始,我在写博客了,因为我觉得业余写写博客也还是很不错的,但是从2017年下半年开始,百度已经推出了原创保护功能和熊掌号平台,为此,我也提交了不少以前的老数据,而这些历史...

原创小博客 ⋅ 今天 ⋅ 0

LVM讲解、磁盘故障小案例

LVM LVM就是动态卷管理,可以将多个硬盘和硬盘分区做成一个逻辑卷,并把这个逻辑卷作为一个整体来统一管理,动态对分区进行扩缩空间大小,安全快捷方便管理。 1.新建分区,更改类型为8e 即L...

蛋黄Yolks ⋅ 今天 ⋅ 0

Hadoop Yarn调度器的选择和使用

一、引言 Yarn在Hadoop的生态系统中担任了资源管理和任务调度的角色。在讨论其构造器之前先简单了解一下Yarn的架构。 上图是Yarn的基本架构,其中ResourceManager是整个架构的核心组件,它负...

p柯西 ⋅ 今天 ⋅ 0

uWSGI + Django @ Ubuntu

创建 Django App Project 创建后, 可以看到路径下有一个wsgi.py的问题 uWSGI运行 直接命令行运行 利用如下命令, 可直接访问 uwsgi --http :8080 --wsgi-file dj/wsgi.py 配置文件 & 运行 [u...

袁祾 ⋅ 今天 ⋅ 0

JVM堆的理解

在JVM中,我们经常提到的就是堆了,堆确实很重要,其实,除了堆之外,还有几个重要的模块,看下图: 大 多数情况下,我们并不需要关心JVM的底层,但是如果了解它的话,对于我们系统调优是非常...

不羁之后 ⋅ 昨天 ⋅ 0

推荐:并发情况下:Java HashMap 形成死循环的原因

在淘宝内网里看到同事发了贴说了一个CPU被100%的线上故障,并且这个事发生了很多次,原因是在Java语言在并发情况下使用HashMap造成Race Condition,从而导致死循环。这个事情我4、5年前也经历...

码代码的小司机 ⋅ 昨天 ⋅ 2

聊聊spring cloud gateway的RetryGatewayFilter

序 本文主要研究一下spring cloud gateway的RetryGatewayFilter GatewayAutoConfiguration spring-cloud-gateway-core-2.0.0.RC2-sources.jar!/org/springframework/cloud/gateway/config/G......

go4it ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部