当前位置:网站首页>堆排序【手写小根堆】
堆排序【手写小根堆】
2022-07-06 09:18:00 【小陈同学_】
一、什么是堆呢?
堆是一个高效的优先级队列,我们可以把堆看做一棵完全二叉树的数组。
性质:
- 堆中某个结点的值总是不大于或不小于其父结点的值
- 堆总是一棵完全二叉树
根结点最大的堆叫做最大堆或大根堆,根结点最小的堆叫做最小堆或小根堆。
算法思想及操作(小根堆为例):
将要排序的所有值放到一棵完全二叉树的各个结点中,这时候的二叉树不用具备堆的性质,利用up或者down操作来调整堆。
在堆的创建过程中,我们需要加入两个操作:
- 向上调整法(up)【建堆】
从最后一个节点开始调整,跟它的父节点比较,如果比父节点小,则不符合小根堆的性质,因此需要交换,否则不需要交换。
调成完一个节点后,把该节点的父节点看做当前结点,继续做调整。
以此类推,即可调整成堆。 - 向下调整法(down)
设父节点为fa,左儿子为l,右儿子为r。
从最后一个非叶子节点(即第n/2个节点)开始,用fa分别与l和r作比较,最小的儿子做交换,如果fa已经是最小的,则不需要交换。
同向上调整法一样,调整完之后,从最小的儿子当做fa,继续做向下调整法。
为什么是从最后一个非叶子节点开始down呢?
图中的值是节点编号,一共有9个节点,那么n=9,所以从n/2开始调整就是从第四个节点开始调整(红色节点)。
这是为什么呢?
因为我们执行的是down操作,那么为了调整到所有的点,必然要调整到最后一个叶子结点。恰巧最后一个叶子结点的父节点就是第n/2个节点,从n/2个节点开始down,肯定会调整到所有的点。
下面来看一下模拟过程:
初始状态图
现在就建好了一个小根堆(注意小根堆和大根堆不唯一,满足性质即可)
下面利用堆来排序:
题目:堆排序
输入一个长度为 n n n 的整数数列,从小到大输出前 m m m 小的数。
输入格式
第一行包含整数 n n n 和 m m m。
第二行包含 n 个整数,表示整数数列。
输出格式
共一行,包含 m m m 个整数,表示整数数列中前 m 小的数。
数据范围
1 ≤ m ≤ n ≤ 105 1≤m≤n≤105 1≤m≤n≤105,
1 ≤ 数 列 中 元 素 ≤ 109 1≤数列中元素≤109 1≤数列中元素≤109
输入样例:
5 3
4 5 1 3 2
输出样例:
1 2 3
题目思路:
此题要输出用堆排序后的前k个数,因为堆并不能保证从左到右、从上到下的顺序是依次递增的,比如下图中第三个数为5,实际上第三个数应该为4,所以我们不能建好堆之后直接输出前k个数字。
所以可以利用删除节点(并不是真正意义上的删除)来实现堆排序,删除哪个结点是比较合适的呢,显然不可能是前面和中间的节点,因为在堆中删除前面一个节点是非常麻烦的,但是删除最后一个节点是很容易的。那么删除最后一个节点可不可以呢?答案是可以的,因为堆顶元素保证是最小的一个,所以每次输出了堆顶元素后可以把堆顶元素和最后一个元素交换,此时最小的元素成为了最后一个元素,可以把他删除掉(已经用不到了),然后从堆顶元素开始down操作,因此我们可以发现依然可以维护堆的性质,所以可以利用删除最后一个节点来实现堆的排序。
堆的存储:
为了方便存储以及实现,堆通常可以利用数组来模拟。
fa:父节点,l:左二子,r:右儿子
设 f a = x fa=x fa=x,则 l = 2 ∗ x l=2*x l=2∗x, r = 2 ∗ x + 1 r=2*x+1 r=2∗x+1
AC代码(C++):
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10;
int q[N],numbers,n,m;
void down(int x){
int t=x;
if(x*2<=numbers && q[x*2]<q[t]) t=x*2;
if(x*2+1<=numbers && q[x*2+1]<q[t]) t=x*2+1;
if(t!=x){
swap(q[t],q[x]);
down(t);
}
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&q[i]);
numbers=n; //删除一个节点后剩余节点的个数
for(int i=n/2;i;i--) down(i);
while(m--){
printf("%d ",q[1]);
q[1]=q[numbers];
numbers--;
down(1);
}
return 0;
}
边栏推荐
- PR 2021 quick start tutorial, first understanding the Premiere Pro working interface
- SSD technical features
- The master of double non planning left the real estate company and became a programmer with an annual salary of 25W. There are too many life choices at the age of 25
- Containers and Devops: container based Devops delivery pipeline
- Lean product development - Lean Software Development & lean product development
- Guided package method in idea
- [Nodejs] 20. Koa2 onion ring model ----- code demonstration
- idea中导包方法
- How to improve the deletion speed of sequential class containers?
- Unity3D基础入门之粒子系统(属性介绍+火焰粒子系统案例制作)
猜你喜欢
Teach you to release a DeNO module hand in hand
SVN更新后不出现红色感叹号
Halcon knowledge: gray_ Tophat transform and bottom cap transform
【无标题】
Esp8266 connect onenet (old mqtt mode)
Programming homework: educational administration management system (C language)
Force buckle 1189 Maximum number of "balloons"
FairyGUI增益BUFF數值改變的顯示
idea中好用的快捷键
341. Flatten nested list iterator
随机推荐
基于rtklib源码进行片上移植的思路分享
RTKLIB: demo5 b34f.1 vs b33
What are the functions and features of helm or terrain
First use of dosbox
[offer18] delete the node of the linked list
[offer9] implement queues with two stacks
Unity scene jump and exit
[offer78]合并多个有序链表
Halcon knowledge: gray_ Tophat transform and bottom cap transform
MySQL replacement field part content
In 2020, the average salary of IT industry exceeded 170000, ranking first
GPS高程拟合抗差中误差的求取代码实现
数据库课程设计:高校教务管理系统(含代码)
PR 2021 quick start tutorial, first understanding the Premiere Pro working interface
基本Dos命令
What is the maximum length of MySQL varchar field
idea中好用的快捷键
FairyGUI人物状态弹窗
GNSS定位精度指标计算
【GNSS数据处理】赫尔默特(helmert)方差分量估计解析及代码实现