当前位置:网站首页>Heap sort [handwritten small root heap]
Heap sort [handwritten small root heap]
2022-07-06 12:57:00 【Classmate Chen_】
One 、 What is a heap ?
Heap is an efficient priority queue , We can think of the heap as an array of complete binary trees .
nature :
- The value of a node in the heap is always not greater than or less than the value of its parent node
- The heap is always a complete binary tree
The heap with the largest root node is called maximum heap or large root heap , The heap with the smallest root node is called the smallest heap or small root heap .
Algorithm idea and operation ( Take the small root pile for example ):
Put all the values to be sorted into each node of a complete binary tree , At this time, the binary tree does not have the nature of heap , utilize up perhaps down Operation to adjust the heap .
During the creation of the heap , We need to add two operations :
- Upward adjustment method (up)【 Building the heap 】
Adjust from the last node , Compare with its parent node , If it is smaller than the parent node , It does not conform to the nature of small root pile , So we need to exchange , Otherwise, there is no need to exchange .
After adjusting to a node , Regard the parent node of this node as the current node , Continue to make adjustments .
And so on , It can be adjusted into piles . - Downward adjustment method (down)
Set the parent node to fa, Left son for l, The right son is r.
From the last non-leaf node ( That is to say n/2 Nodes ) Start , use fa Respectively with l and r The comparison , The youngest son in exchange , If fa Is already the smallest , There is no need to exchange .
The same as the upward adjustment method , After adjustment , From the youngest son as fa, Continue to do downward adjustment .
Why start with the last non leaf node down Well ?
The value in the figure is the node number , Altogether 9 Nodes , that n=9, So from n/2 Start adjusting from the fourth node ( Red nodes ).
Why is that ?
Because what we do is down operation , So in order to adjust to all points , It must be adjusted to the last leaf node . It happens that the parent node of the last leaf node is the n/2 Nodes , from n/2 Nodes start down, It will definitely adjust to all points .
Let's take a look at the simulation process :
Initial state diagram
Now we have built a small root pile ( Note that small root pile and large root pile are not unique , Just meet the nature )
Next, use the heap to sort :
subject : Heap sort
Enter a length of n n n The whole number sequence of , From small to large, before output m m m Small number .
Input format
The first line contains integers n n n and m m m.
The second line contains n It's an integer , Represents an integer sequence .
Output format
All in one line , contain m m m It's an integer , Represents the first in an integer sequence m Small number .
Data range
1 ≤ m ≤ n ≤ 105 1≤m≤n≤105 1≤m≤n≤105,
1 ≤ Count Column in element plain ≤ 109 1≤ The elements in the sequence ≤109 1≤ Count Column in element plain ≤109
sample input :
5 3
4 5 1 3 2
sample output :
1 2 3
Topic ideas :
This question is to output the top k Number , Because heap is not guaranteed from left to right 、 The order from top to bottom is increasing , For example, the third number in the figure below is 5, Actually, the third number should be 4, So we can't build a heap and output it directly before k A digital .
So you can delete nodes ( It's not really deletion ) To implement heap sorting , Which node is more appropriate to delete , Obviously, it can't be the front and middle nodes , Because deleting the previous node in the heap is very troublesome , But deleting the last node is easy . Can I delete the last node ? The answer is yes , Because the top element is guaranteed to be the smallest , So every time you output the top of the heap element, you can exchange the top of the heap element with the last element , At this time, the smallest element becomes the last element , You can delete it ( I can't use it anymore ), Then start with the top element down operation , Therefore, we can find that the nature of the heap can still be maintained , So you can delete the last node to sort the heap .
Heap storage :
In order to facilitate storage and implementation , Heaps can usually be modeled using arrays .
fa: Parent node ,l: Left second son ,r: Right son
set up f a = x fa=x fa=x, be l = 2 ∗ x l=2*x l=2∗x, r = 2 ∗ x + 1 r=2*x+1 r=2∗x+1
AC Code (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; // The number of remaining nodes after deleting a node
for(int i=n/2;i;i--) down(i);
while(m--){
printf("%d ",q[1]);
q[1]=q[numbers];
numbers--;
down(1);
}
return 0;
}
边栏推荐
- [算法] 剑指offer2 golang 面试题3:前n个数字二进制形式中1的个数
- Derivation of logistic regression theory
- Code example of MATLAB reading GNSS observation value o file
- [rtklib 2.4.3 B34] version update introduction I
- GNSS定位精度指标计算
- IText 7 generate PDF summary
- Wechat applet development experience
- Unity3d makes the registration login interface and realizes the scene jump
- 《软件测试》习题答案:第一章
- InnoDB dirty page refresh mechanism checkpoint in MySQL
猜你喜欢
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
Code example of MATLAB reading GNSS observation value o file
抗差估计在rtklib的pntpos函数(标准单点定位spp)中的c代码实现
闇の連鎖(LCA+树上差分)
Fairygui loop list
[algorithm] sword finger offer2 golang interview question 2: binary addition
Wechat applet development experience
[algorithm] sword finger offer2 golang interview question 5: maximum product of word length
[算法] 剑指offer2 golang 面试题1:整数除法
Unity3d makes the registration login interface and realizes the scene jump
随机推荐
Affichage du changement de valeur du Buff de gain de l'interface graphique de défaillance
PRIDE-PPPAR源码解析
How to reduce the shutdown time of InnoDB database?
It has been solved by personal practice: MySQL row size too large (> 8126) Changing some columns to TEXT or BLOB or using ROW_ FORMAT
Matlab读取GNSS 观测值o文件代码示例
Knowledge system of digital IT practitioners | software development methods -- agile
【干货】提升RTK模糊度固定率的建议之周跳探测
Liste des boucles de l'interface graphique de défaillance
Prove the time complexity of heap sorting
[算法] 剑指offer2 golang 面试题8:和大于或等于k的最短子数组
Mysql database reports an error: row size too large (> 8126) Changing some columns to TEXT or BLOB or using ROW_ FORMAT=DY
KF UD分解之UD分解基础篇【1】
[算法] 剑指offer2 golang 面试题12:左右两边子数组的和相等
[algorithm] sword finger offer2 golang interview question 13: sum of numbers of two-dimensional submatrix
记录:Navicat Premium初次无法连接数据库MySQL之解决
3月15号 Go 1.18 正式版发布 了解最新特色以及使用方法
Unity3D摄像机,键盘控制前后左右上下移动,鼠标控制旋转、放缩
抗差估计在rtklib的pntpos函数(标准单点定位spp)中的c代码实现
Fairygui loop list
Naive Bayesian theory derivation