从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)(下)

简介: 从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)

从C语言到C++_19(容器适配器+stack和queue模拟实现+优先级队列priority_queue)(中):https://developer.aliyun.com/article/1521888

4.2 priority_queue的使用

优先级队列默认使用 vector 作为其底层存储数据的容器,

在 vector 上又使用了堆算法将 vector 中元素构造成堆的结构,因为 priority_queue 就是堆。

所有需要用到堆的地方,都可以考虑使用 priority_queue。

值得注意的是,priority_queue 默认为大根堆。注意下面是反过来的:

优先级队列默认大的优先级高,传的是 less 仿函数,底层是一个大堆;

如果想控制小的优先级高,需手动传 greater 仿函数,其底层是一个小堆。

(仿函数后面讲,实现优先级队列时详细讲解,现在只需要知道如何使用即可)

看看文档使用:

常用接口函数:

代码使用:(包的是queue的头文件)

#include <iostream>
#include <queue>
using namespace std;
 
void test_priority_queue()
{
    priority_queue<int> pq;//默认大堆优先级高
 
    pq.push(3);
    pq.push(1);
    pq.push(2);
    pq.push(5);
    pq.push(0);
    pq.push(8);
    pq.push(1);
 
    while (!pq.empty())
    {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
 
    // 迭代器区间初始化:原生指针也是迭代器
    int arr[] = { 3, 2, 7, 6, 0, 4, 5, 9, 8, 1 };
    priority_queue<int> heap(arr, arr+sizeof(arr)/sizeof(arr[0]));
 
    while (!heap.empty())
    {
        cout << heap.top() << " ";
        heap.pop();
    }
    cout << endl;
}
int main()
{
    //test_stack();
    //test_queue();
    test_priority_queue();
 
    return 0;
}

默认是用 vector 存储的,注意这里没有明确指定 less 还是 greater,所以默认为 less。

令该优先级队列以小的优先级高:在定义优先级队列时主动去传 greater<int>

(包一下头文件functional)因为传 greater<int> 是在第三个参数接收的,

如果你想传第三个模板参数,你必须得先传第二个(下面是定义,仔细观察缺省值部分)

代码演示小的优先级高:

#include <iostream>
#include <queue>
#include <vector> 
#include <functional> // greater和less的头文件
using namespace std;
 
void test_priority_queue()
{
    priority_queue<int, vector<int>, greater<int>> pq;
 
    pq.push(3);
    pq.push(1);
    pq.push(2);
    pq.push(5);
    pq.push(0);
    pq.push(8);
    pq.push(1);
 
    while (!pq.empty())
    {
        cout << pq.top() << " ";
        pq.pop();
    }
    cout << endl;
 
    // 迭代器区间初始化:原生指针也是迭代器
    int arr[] = { 3, 2, 7, 6, 0, 4, 5, 9, 8, 1 };
    priority_queue<int, vector<int>, greater<int>> heap(arr, arr+sizeof(arr)/sizeof(arr[0]));
 
    while (!heap.empty())
    {
        cout << heap.top() << " ";
        heap.pop();
    }
    cout << endl;
}
int main()
{
    //test_stack();
    //test_queue();
    test_priority_queue();
 
    return 0;
}

值得注意的是如果在priority_queue中放自定义类型的数据,

用户需要在自定义类型中提供> 或者< 的重载。(像日期类一样)

4.3 priority_queue解决TopK问题

剑指 Offer II 076. 数组中的第 k 大的数字 - 力扣(LeetCode)

215. 数组中的第K个最大元素 - 力扣(LeetCode)

(这两题是一样的,我们在讲TopK问题的时候也用C语言写过:)

数据结构与算法⑬(第四章_中_续二)堆解决Topk问题+堆的概念选择题_GR C的博客-CSDN博客

难度中等

给定整数数组 nums 和整数 k,请返回数组中第 k 个最大的元素。

请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。

示例 1:

输入:

[3,2,1,5,6,4],

k = 2

输出: 5

示例 2:

输入:

[3,2,3,1,2,4,5,5,6],

k = 4

输出: 4

提示:

1 <= k <= nums.length <= 10^5

-10^4 <= nums[i] <= 10^4

int findKthLargest(int* nums, int numsSize, int k){
 
}

解析代码:(sort一下也能过,但是时间是O(N*logN))

和以前一样:这里我们需要把整个数组建成一个大堆,然后pop(k-1)次堆顶的元素后堆顶的元素

就是第k大的数。而且我们不用自己写大堆下调算法了,建堆也可以直接用priority_queue:

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        //把整个数组建成一个大堆,(O(N))
        priority_queue<int> MaxHeap(nums.begin(),nums.end());
 
        while(--k)//然后pop(k-1)次堆顶的元素(log(N*K))
        {
            MaxHeap.pop();
        }
        return MaxHeap.top();//堆顶的元素就是第k大的数
    }
};

看下C语言写的:(调整算法后面模拟实现priority_queue还会用,面试可能也要写)

void Swap(int* px, int* py)
{
    int tmp = *px;
    *px = *py;
    *py = tmp;
}
 
void justDown(int* arr, int n, int root)//大堆下调
{
    int father = root;
    int child = father * 2 + 1;//默认左孩子大
    while (child < n)
    {
        if (child + 1 < n && arr[child] < arr[child + 1])
        {  // 如果右孩子存在且右孩子比左孩子大
            child++;
        }
        if (arr[father] < arr[child])
        {
            Swap(&arr[father], &arr[child]);
 
            father = child;
            child = father * 2 + 1;
        }
        else
        {
            break;
        }
    }
}
 
int findKthLargest(int* nums, int numsSize, int k) {
    for (int i = (numsSize - 1 - 1) / 2;i >= 0;i--) //建堆的for写法
    {
        justDown(nums, numsSize, i);
    }
    // 删除数据
    for (int i = 1;i <= k - 1;i++)
    {
        Swap(&nums[0], &nums[numsSize - i]);
        justDown(nums, numsSize - i, 0);//删除多少个numsize-多少个
    }
    return nums[0];
}

本章完。

下一部分:模拟实现 priority_queue,过程中讲STL六大组件之一的仿函数,然后是反向迭代器。

目录
相关文章
|
4月前
|
存储 搜索推荐 C++
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器2
【C++篇】深度剖析C++ STL:玩转 list 容器,解锁高效编程的秘密武器
94 2
|
3月前
|
存储 设计模式 C++
【C++】优先级队列(容器适配器)
本文介绍了C++ STL中的线性容器及其适配器,包括栈、队列和优先队列的设计与实现。详细解析了`deque`的特点和存储结构,以及如何利用`deque`实现栈、队列和优先队列。通过自定义命名空间和类模板,展示了如何模拟实现这些容器适配器,重点讲解了优先队列的内部机制,如堆的构建与维护方法。
58 0
|
4月前
|
存储 编译器 C++
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
103 2
|
2月前
|
监控 NoSQL 时序数据库
《docker高级篇(大厂进阶):7.Docker容器监控之CAdvisor+InfluxDB+Granfana》包括:原生命令、是什么、compose容器编排,一套带走
《docker高级篇(大厂进阶):7.Docker容器监控之CAdvisor+InfluxDB+Granfana》包括:原生命令、是什么、compose容器编排,一套带走
294 78
|
1月前
|
Ubuntu NoSQL Linux
《docker基础篇:3.Docker常用命令》包括帮助启动类命令、镜像命令、有镜像才能创建容器,这是根本前提(下载一个CentOS或者ubuntu镜像演示)、容器命令、小总结
《docker基础篇:3.Docker常用命令》包括帮助启动类命令、镜像命令、有镜像才能创建容器,这是根本前提(下载一个CentOS或者ubuntu镜像演示)、容器命令、小总结
150 6
《docker基础篇:3.Docker常用命令》包括帮助启动类命令、镜像命令、有镜像才能创建容器,这是根本前提(下载一个CentOS或者ubuntu镜像演示)、容器命令、小总结
|
2月前
|
监控 Docker 容器
在Docker容器中运行打包好的应用程序
在Docker容器中运行打包好的应用程序
|
2月前
|
Ubuntu Linux 开发工具
docker 是什么?docker初认识之如何部署docker-优雅草后续将会把产品发布部署至docker容器中-因此会出相关系列文章-优雅草央千澈
Docker 是一个开源的容器化平台,允许开发者将应用程序及其依赖项打包成标准化单元(容器),确保在任何支持 Docker 的操作系统上一致运行。容器共享主机内核,提供轻量级、高效的执行环境。本文介绍如何在 Ubuntu 上安装 Docker,并通过简单步骤验证安装成功。后续文章将探讨使用 Docker 部署开源项目。优雅草央千澈 源、安装 Docker 包、验证安装 - 适用场景:开发、测试、生产环境 通过以上步骤,您可以在 Ubuntu 系统上成功安装并运行 Docker,为后续的应用部署打下基础。
95 5
docker 是什么?docker初认识之如何部署docker-优雅草后续将会把产品发布部署至docker容器中-因此会出相关系列文章-优雅草央千澈
|
2月前
|
存储 Kubernetes 开发者
容器化时代的领航者:Docker 和 Kubernetes 云原生时代的黄金搭档
Docker 是一种开源的应用容器引擎,允许开发者将应用程序及其依赖打包成可移植的镜像,并在任何支持 Docker 的平台上运行。其核心概念包括镜像、容器和仓库。镜像是只读的文件系统,容器是镜像的运行实例,仓库用于存储和分发镜像。Kubernetes(k8s)则是容器集群管理系统,提供自动化部署、扩展和维护等功能,支持服务发现、负载均衡、自动伸缩等特性。两者结合使用,可以实现高效的容器化应用管理和运维。Docker 主要用于单主机上的容器管理,而 Kubernetes 则专注于跨多主机的容器编排与调度。尽管 k8s 逐渐减少了对 Docker 作为容器运行时的支持,但 Doc
165 5
容器化时代的领航者:Docker 和 Kubernetes 云原生时代的黄金搭档
|
1月前
|
Kubernetes Linux 虚拟化
入门级容器技术解析:Docker和K8s的区别与关系
本文介绍了容器技术的发展历程及其重要组成部分Docker和Kubernetes。从传统物理机到虚拟机,再到容器化,每一步都旨在更高效地利用服务器资源并简化应用部署。容器技术通过隔离环境、减少依赖冲突和提高可移植性,解决了传统部署方式中的诸多问题。Docker作为容器化平台,专注于创建和管理容器;而Kubernetes则是一个强大的容器编排系统,用于自动化部署、扩展和管理容器化应用。两者相辅相成,共同推动了现代云原生应用的快速发展。
147 11
|
2月前
|
关系型数据库 应用服务中间件 PHP
实战~如何组织一个多容器项目docker-compose
本文介绍了如何使用Docker搭建Nginx、PHP和MySQL的环境。首先启动Nginx容器并查看IP地址,接着启动Alpine容器并安装curl测试连通性。通过`--link`方式或`docker-compose`配置文件实现服务间的通信。最后展示了Nginx配置文件和PHP代码示例,验证了各服务的正常运行。
81 3
实战~如何组织一个多容器项目docker-compose

热门文章

最新文章