文档章节

priority_queue优先队列/C++

Frank-yang
 Frank-yang
发布于 2017/09/04 11:22
字数 592
阅读 46
收藏 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
广州
私信 提问
STL系列之五 priority_queue 优先级队列

priority_queue 优先级队列是一个拥有权值概念的单向队列queue,在这个队列中,所有元素是按优先级排列的(也可以认为queue是个按进入队列的先后做为优先级的优先级队列——先进入队列的元素...

彭博
2012/04/12
1K
0
STL系列之五 priority_queue 优先级队列

priority_queue 优先级队列是一个拥有权值概念的单向队列queue,在这个队列中,所有元素是按优先级排列的(也可以认为queue是个按进入队列的先后做为优先级的优先级队列——先进入队列的元素...

长平狐
2012/12/10
60
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

没有更多内容

加载失败,请刷新页面

加载更多

Spring源码学习笔记-1-Resource

打算补下基础,学习下Spring源码,参考书籍是《Spring源码深度解析》,使用版本是Spring 3.2.x,本来想试图用脑图记录的,发现代码部分不好贴,还是作罢,这里只大略记录下想法,不写太细了 ...

zypy333
今天
10
0
RestClientUtil和ConfigRestClientUtil区别说明

RestClientUtil directly executes the DSL defined in the code. ConfigRestClientUtil gets the DSL defined in the configuration file by the DSL name and executes it. RestClientUtil......

bboss
今天
17
0

中国龙-扬科
昨天
2
0
Linux系统设置全局的默认网络代理

更改全局配置文件/etc/profile all_proxy="all_proxy=socks://rahowviahva.ml:80/"ftp_proxy="ftp_proxy=http://rahowviahva.ml:80/"http_proxy="http_proxy=http://rahowviahva.ml:80/"......

临江仙卜算子
昨天
11
0
java框架学习日志-6(bean作用域和自动装配)

本章补充bean的作用域和自动装配 bean作用域 之前提到可以用scope来设置单例模式 <bean id="type" class="cn.dota2.tpye.Type" scope="singleton"></bean> 除此之外还有几种用法 singleton:......

白话
昨天
10
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部