AcWing | 堆排序 叁歲伎倆 2022-12-20 01:56 121阅读 0赞 **题目内容** > 输入一个长度为n的整数数列,从小到大输出前m小的数。 输入格式 > > 第一行包含整数n和m。 > > 第二行包含n个整数,表示整数数列。 **输出格式** > 共一行,包含m个整数,表示整数数列中前m小的数。 **数据范围** > 1≤m≤n≤105 , 1≤数列中元素≤109 **输入样例:** 5 3 4 5 1 3 2 **输出样例:** 1 2 3 -------------------- **思路:** * 堆:是一棵完全二叉树(即除了叶节点以外,所有节点都是非空,且叶节点从左到右排列) * 例如小根堆:每个节点都小于等于其左右子节点 * 堆如何存储? * 设根节点为x,则其左儿子是2x,右儿子是2x+1 * 堆的两个函数:因为一开始建堆的时候是没有考虑顺序的,所以要用这两个操作调整成小/大根堆 * down:节点下移 * up:节点上移 * 堆的基本操作,对于小根堆,且下标从1开始: * 插入一个数 `heap[++size];up(size);` * 求集合当中的最小值 `heap[1];` * 删除最小值 `heap[1]=heap[size];size--;down(1);`(调换到末尾再删除,因为我们用数组维护堆的话,删头节点很麻烦但是尾节点很方便) * 删除任何一个元素 `heap[k]=heap[size];size--;down(k);up(k);`(down和up总会执行一个 省去了判断) * 修改任何一个元素`heap[k]=x;down(k);up(k);` **时间复杂度分析**:求最小值O(1);插入和删除操作O(logn);down/up操作O(logn),和树的高度成正比; **完整代码:** #include<iostream> #include<algorithm> using namespace std; const int N=100010; int n,m; int h[N],sizeh; void down(int u){ int t=u;//t表示三个点(父节点、左右子节点)里面最小值 if(u*2<=sizeh &&h[u*2]<h[t])t=u*2;//如果左儿子存在,且小于t,将小的值赋给t if(u*2+1<=sizeh &&h[u*2+1]<h[t] )t=u*2+1; if(u!=t){ //如果u不是t,那就说明根节点不是最小的,那就和最小的交换一下 swap(h[u],h[t]); down(t); } } void up(int u){ while(u/2 &&h[u/2]>h[u]){ swap(h[u/2],h[u]); u/=2; } } int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)scanf("%d",&h[i]); sizeh=n; for(int i=n/2;i;i--)down(i);//O(n)建堆,n/2的时候高度是1 while(m--){ printf("%d ",h[1]);//每次输出当前堆顶元素 h[1]=h[sizeh];//删掉对顶:讲最后一个元素赋到第一个元素上去 sizeh--;//数量减少 down(1);//从上向下维护堆 } return 0; }
相关 AcWing | 堆排序 题目内容 > 输入一个长度为n的整数数列,从小到大输出前m小的数。 输入格式 > > 第一行包含整数n和m。 > > 第二行包含n个整数,表示整数数列。 输出格式 > 叁歲伎倆/ 2022年12月20日 01:56/ 0 赞/ 122 阅读
相关 排序-堆排序 1.堆排序前言 前面博客中讲到简单选择排序,它在待排序的n个记录中选择一个最小的记录需要比较n-1次。本来这也可以理解,查找第一个数据需要比较这么多次是正常的,否则如何知 旧城等待,/ 2022年09月30日 06:45/ 0 赞/ 195 阅读
相关 【排序】堆排序 堆的定义 设有n个元素的序列 k1,k2,…,kn,当且仅当满足下述关系之一时,称之为堆。 ![图示][SouthEast] 解释:如果让满足以上条件的元素序列 (k 分手后的思念是犯贱/ 2022年06月18日 11:47/ 0 赞/ 233 阅读
相关 看懂堆排序——堆与堆排序(三) 看懂堆排序——堆与堆排序(三) 看懂堆排序——堆与堆排序(三) 堆排序的基本思想 代码详解 偏执的太偏执、/ 2022年05月25日 06:52/ 0 赞/ 253 阅读
相关 排序——堆排序 堆排序代码 include <iostream> using namespace std; include <stdio.h> in 墨蓝/ 2022年05月21日 12:05/ 0 赞/ 225 阅读
相关 堆排序 什么是堆排序,堆排序能解决什么问题? 在排序的过程中,不能把进行排序的过程中,得一些信息保留下来吗?来加快排序的速度吗?答案是可以的。通过利用完全二叉堆的结构来保留信息。 迷南。/ 2021年10月29日 07:20/ 0 赞/ 335 阅读
相关 堆和堆排序 堆排序 堆排序基本介绍 1. 堆排序是利用堆这种数据结构而设计的一种排序算法,堆排序是一种选择排序,它的最坏,最好,平均时间复 杂度均为 O(nlogn),它也 柔光的暖阳◎/ 2021年10月19日 21:12/ 0 赞/ 338 阅读
相关 堆排序 文章目录 一、堆排序介绍 二、如何进行堆排序 一、堆排序介绍 百度百科: 堆排序(Heapsort)是指利用堆积树 我会带着你远行/ 2021年10月18日 16:46/ 0 赞/ 326 阅读
相关 排序-堆排序 [2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][] 在说明堆排序的过程前得先了解什么是堆: 先看下图(来源 清疚/ 2021年09月20日 03:22/ 0 赞/ 398 阅读
相关 堆排序 堆排序的特点是:在排序过程中,将待排序数组看成是一棵完全二叉树的顺序存储结构,利用完全二叉树中父结点和子结点之间的内在关系,在当前无序区中选择关键字最大(或最小) 不念不忘少年蓝@/ 2021年09月17日 00:16/ 0 赞/ 421 阅读
还没有评论,来说两句吧...