文档章节

priority_queue优先队列/C++

Frank-yang
 Frank-yang
发布于 2017/09/04 11:22
字数 592
阅读 28
收藏 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
数据结构&堆&heap&priority_queue&实现

目录 什么是堆? 大根堆 小根堆 堆的操作 STL queue 什么是堆? 堆是一种数据结构,可以用来实现优先队列 大根堆 大根堆,顾名思义就是根节点最大。我们先用小根堆的建堆过程学习堆的思想。 ...

Chicago_01
09/21
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

没有更多内容

加载失败,请刷新页面

加载更多

Android WebView制作简易浏览器

最终效果 先创建一个WebView控件,其他的就是通过线性布局在上方加入网址输入框和两个按钮 <WebView android:id="@+id/act_webview_wv" android:layout_width="ma...

lanyu96
3分钟前
0
0
解决MacOS升级系统Sierra到Mojave后git报错

错误信息 升级MacOS Sierra到Mac Mojave后执行git命令报错: xcrun: error: invalid active developer path (/Library/Developer/CommandLineTools), missing xcrun at: /Library/Developer/......

阿dai
4分钟前
0
0
兄弟连区块链教程以太源码分析CMD深入分析(一)

cmd包分析 cmd下面总共有13个子包,除了util包之外,每个子包都有一个主函数,每个主函数的init方法中都定义了该主函数支持的命令,如 geth包下面的: func init() { // Initialize the...

兄弟连区块链入门教程
6分钟前
0
0
Titan Framework MongoDB深入理解1

在TitanFrameWork框架中,已经集成了MongoDB的各个功能,现在我们对框架内部的一些重要类进行分析与解读。 MongoDBConverter 在Titan框架中,比较重要的一个接口就是MongoDBConverter,它是作...

云季科技
11分钟前
0
0
SpringBoot集成Quartz

SpringBoot集成Quartz 什么是Quartz Quartz is a richly featured, open source job scheduling library that can be integrated within virtually any Java application - from the smalle......

Grittan
15分钟前
0
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部