[C++][算法基础]堆排序(堆)

输入一个长度为 n 的整数数列,从小到大输出前 m 小的数。

输入格式

第一行包含整数 n 和 m。

第二行包含 n 个整数,表示整数数列。

输出格式

共一行,包含 m 个整数,表示整数数列中前 m 小的数。

数据范围

1≤m≤n≤10^{5}
1≤数列中元素≤10^{9}

输入样例:
5 3
4 5 1 3 2
输出样例:
1 2 3

代码:

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 100010;
int heap[N],l;
int n,m;

void down(int now){
    int target = now;
    if(2*now <= l && heap[2*now] < heap[target]){
        target = 2 * now;
    }
    if(2*now + 1<= l && heap[2*now + 1] < heap[target]){
        target = 2 * now + 1;
    }
    if(target != now){
        swap(heap[target],heap[now]);
        down(target);
    }
}

int main(){
    cin>>n>>m;
    for(int i = 1;i<=n;i++){
        cin>>heap[i];
    }
    l = n;
    for(int i = n/2;i>0;i--){
        down(i);
    }
    while(m--){
        cout<<heap[1]<<" ";
        heap[1] = heap[l];
        l--;
        down(1);
    }
    return 0;
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/525436.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

真实的招生办对话邮件及美国高校官网更新的反 AI 政策

这两年 ChatGPT 的热度水涨船高&#xff0c;其编写功能强大&#xff0c;且具备强大的信息整合效果&#xff0c;所以呈现的内容在一定程度上具备可读性。 那么&#xff0c;美国留学文书可以用 ChatGPT 写吗&#xff1f;使用是否有风险&#xff1f;外网博主 Kushi Uppu 在这个申…

C++ vector顺序表模拟实现

目录 前言&#xff1a; 模拟实现&#xff1a; 构造函数&#xff1a; 析构函数&#xff1a; 容量调整&#xff08;reserve&#xff09;&#xff1a; resize函数&#xff1a; 尾插&#xff08;push_back&#xff09;: 尾删&#xff08;pop_back&#xff09;: 插入&#xff…

基于Spring boot+Vue的业余排球俱乐部会员管理系统

5 系统功能模块的具体实现 5.1超级会员角色 5.1.1 登录 超级管理员登录通过用户名和密码去数据库查询用户表&#xff0c;该名称是否在用户表中存在&#xff0c;如果存在&#xff0c;则通过用户名和密码查询密码是否正确&#xff0c;然后吧用户的信息存在jwt的负载里&#xf…

表1和表2怎么查找相同的内容?3种实用技巧赶紧学起来

-- 为啥会感觉给不了一个人幸福&#xff0c;而选择分开不打扰&#xff1f; 核对不同工作表中的数据&#xff0c;是大家在处理工作表时会遇到的高频场景&#xff0c;这篇文章跟大家分享一下如何查找不同工作表中的相同内容。 比对数据的方法有很多&#xff0c;这里跟大家分享3种…

LangChain - OpenGPTs

文章目录 MessageGraph 消息图认知架构AssistantsRAGChatBot 持久化配置新模型新工具astream_events总结 关键链接&#xff1a; OpenGPT GitHub 存储库YouTube 上的 OpenGPT 演练LangGraph&#xff1a;Python、JS 两个多月前&#xff0c;在 OpenAI 开发日之后&#xff0c;我们…

二维码门楼牌管理应用平台建设:打造便民服务热线新生态

文章目录 前言一、二维码门楼牌管理应用平台概述二、便民热线服务的构建三、便民热线服务的优势四、便民热线服务的潜在价值五、总结与展望 前言 随着信息技术的飞速发展&#xff0c;二维码门楼牌管理应用平台的建设已成为城市智慧化建设的重要组成部分。这一平台不仅为居民提…

区块链技术与数字身份:解析Web3的身份验证系统

在数字化时代&#xff0c;随着个人数据的日益增多和网络安全的日益关注&#xff0c;传统的身份验证系统面临着越来越多的挑战和限制。在这种背景下&#xff0c;区块链技术的出现为解决这一问题提供了全新的思路和解决方案。Web3作为一个去中心化的互联网模式&#xff0c;其身份…

MySQL学习笔记------多表查询

目录 多表关系 一对多 多对多 一对一 多表查询 概述 分类 内连接&#xff08;交集&#xff09; 隐式内连接 显式内连接 ​编辑 外连接&#xff08;from后为左表&#xff0c;join后为右表&#xff09; 左外连接 右外连接 自连接 联合查询&#xff08;union&#…

APP的UI设计规范

APP的设计规范是一系列原则和标准&#xff0c;旨在确保应用程序提供一致、易用且美观的用户体验。以下是一些关键的APP设计规范。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xff0c;欢迎交流合作。 1.一致性&#xff1a; 保持界面元素和交互行为的一致性…

Sketch是免费软件吗?这款软件支持导入!

Sketch 是一款针对网页、图标、插图等设计的矢量绘图软件。Sketch 的操作界面非常简单易懂&#xff0c;帮助全世界的设计师创作出许多不可思议的作品。但是同时&#xff0c;Sketch 也有一些痛点&#xff1a;使用 Sketch 需要安装 InVision、Abstract 、Zeplin 等插件&#xff0…

【LeetCode: 455. 分发饼干 + 贪心】

&#x1f680; 算法题 &#x1f680; &#x1f332; 算法刷题专栏 | 面试必备算法 | 面试高频算法 &#x1f340; &#x1f332; 越难的东西,越要努力坚持&#xff0c;因为它具有很高的价值&#xff0c;算法就是这样✨ &#x1f332; 作者简介&#xff1a;硕风和炜&#xff0c;…

Docker 引擎离线安装包采集脚本

文章目录 一、场景说明二、脚本职责三、参数说明四、操作示例五、注意事项 一、场景说明 本自动化脚本旨在为提高研发、测试、运维快速部署应用环境而编写。 脚本遵循拿来即用的原则快速完成 CentOS 系统各应用环境部署工作。 统一研发、测试、生产环境的部署模式、部署结构、…

鼠标不动N秒,电脑自动待机睡眠V1.0

鼠标不动N秒&#xff0c;电脑自动待机睡眠V1.0 开发背景&#xff1a;因为不关电脑多次被罚款&#xff0c;所以下决心做一个自动待机睡眠软件 win系统自带的睡眠小程序&#xff0c;在电脑正在运行其它程序时&#xff0c;只能关闭屏幕而不是电脑待机。 为了电脑深度睡眠待机&a…

基于LNMP环境上线QQ农场

目录 一.介绍 二. 环境准备 三.安装Mysql数据库 四.安装PHP 五.安装Nginx 六.测试Nginx服务于PHP服务是否能关联 七.项目上线 QQ农场源码&#xff1a;做本项目默认操作者有一定的基础知识与理解能力 链接&#xff1a;https://pan.baidu.com/s/1HF8GZ-yvNh7RbJ61nXOW-g?…

吴恩达最新活动演讲 :AI Agent不应该只是执行,而是能够自主思考工作流

AI Agent&#xff0c;作为一种能够感知环境、进行决策和执行动作的智能实体&#xff0c;正逐渐成为人工智能领域的重要发展方向。随着大型语言模型&#xff08;LLM&#xff09;技术的不断进步&#xff0c;AI Agent的应用潜力正在被逐步释放&#xff0c;它们不仅能够执行基于明确…

Linux操作系统上启动redis服务

一、下载安装redis 网上找教程。 二、修改redis.conf配置文件 1.先进入redis目录 2. ls查看文件 3.修改redis.conf中的配置&#xff0c;将daemonize no改成daemonize yes。 输入指令进行修改修改 vi redis.conf 保存退出。 三、启动redis服务 在下载的redis目录下执行以…

13 - Debian如何配置网络(1)

作者&#xff1a;网络傅老师 特别提示&#xff1a;未经作者允许&#xff0c;不得转载任何内容。违者必究&#xff01; Debian如何配置网络&#xff08;1&#xff09; 《傅老师Debian小知识库系列之13》——原创 前言 傅老师Debian小知识库特点&#xff1a; 1、最小化拆解Deb…

特别详细的Spring Cloud 系列教程1:服务注册中心Eureka的启动

Eureka已经被Spring Cloud继承在其子项目spring-cloud-netflix中&#xff0c;搭建Eureka Server的方式还是非常简单的。只需要通过一个独立的maven工程即可搭建Eureka Server。 我们引入spring cloud的依赖和eureka的依赖。 <dependencyManagement><!-- spring clo…

基于李雅普诺夫稳定性分析的一阶、二阶系统MATLAB仿真模型

李雅普诺夫稳定性定理 假设系统状态方程&#xff1a; 零状态为其平衡状态&#xff0c;即f(0,t)0 t&#xff1e;t0。如果存在一个具有连续的一阶偏导数的标量函数V (x,t)&#xff0c;并且满足下述条件&#xff1a; 1、V (x,t)是正定的&#xff1b; 2、沿状态方程轨线的V (x…

CV论文--2024.4.7

1、Know Your Neighbors: Improving Single-View Reconstruction via Spatial Vision-Language Reasoning 中文标题&#xff1a;了解你的邻居&#xff1a;通过空间视觉语言推理改进单视图重建 简介&#xff1a;在计算机视觉领域&#xff0c;从单个视图恢复三维场景几何是一个基…