当前位置:网站首页>Manually implement heap sorting -838 Heap sort
Manually implement heap sorting -838 Heap sort
2022-07-05 04:41:00 【The wind is a little strong】
Heap properties
Pile up (Heap) Is a kind of data structure , They have a tree structure , And it can ensure that the parent node is larger than the child node ( Or small ). When the root node saves the maximum value in the heap , be called Big root pile ; conversely , It is called a Heap .
Binary heap (Binary Heap) It's the simplest 、 Common heap , It is a tree that conforms to the nature of heap Perfect binary tree . It can achieve O(logn) Insert or delete a value , also O(1) Query the largest ( Or the smallest ) value .
Storage
Take the small root pile for example
As a complete binary tree , A binary stack can be used 1-index To store , For the node p,p2 That is, the left son ,p2+1 That is, the right node . meanwhile , use size Record the number of nodes in the current binary heap .
The relevant operation
up(int x): Compare with the root node of the current node , If the current point is smaller than the root node , Exchange with the root node
down(int x): Compare with the left and right sons of the current node , If the left and right sons are a little smaller than the current , Then exchange the younger son with the current point
Templates
// h[N] Store values in the heap , h[1] It's the top of the pile ,x My left son is 2x, The right son is 2x + 1
// ph[k] Store the k The position of an insertion point in the heap
// hp[k] The subscript in the heap is k Which point is inserted
int h[N], ph[N], hp[N], size;
// Swap two points , And its mapping relationship
void heap_swap(int a, int b)
{
swap(ph[hp[a]],ph[hp[b]]);
swap(hp[a], hp[b]);
swap(h[a], h[b]);
}
void down(int u)
{
int t = u;
if (u * 2 <= size && h[u * 2] < h[t]) t = u * 2;
if (u * 2 + 1 <= size && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
if (u != t)
{
heap_swap(u, t);
down(t);
}
}
void up(int u)
{
while (u / 2 && h[u] < h[u / 2])
{
heap_swap(u, u / 2);
u >>= 1;
}
}
// O(n) Building the heap
for (int i = n / 2; i; i -- ) down(i);
subject
Code
#include<iostream>
#include<algorithm>
using namespace std;
const int N=100005;
int h[N],len;
int n,m;
void down(int u){
int t=u; //t Save the subscript of the lowest decimal
if(2*u<=len && h[2*u]<h[t]){
// Subscript to be u My point has a left son , The left son is smaller
t=2*u; // The youngest is the left son
}
if(2*u+1<=len && h[2*u+1]<h[t]){
// Subscript to be u The right son of is smaller than the current youngest
t=2*u+1; // The youngest is the right son
}
if(u!=t){
// If the current value is not the minimum , So update
swap(h[u],h[t]); // Exchange the smallest to u The location of
down(t); // Recursive current (2u+1) The following values
}
}
void up(int u){
if(u/2>=1 && h[u/2]>h[u]){
// There is a parent node ,
swap(h[u/2],h[u]);
up(u/2);
}
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>h[i];
}
len=n;
for(int i=n/2;i>0;i--){
// Because the last layer has no child nodes , So just cycle n/2 That's it .
down(i);
}
while(m--){
cout<<h[1]<<" ";
h[1]=h[len]; // After taking out the minimum value , Put the last value in the first position , Total number minus one , then down
len--;
down(1);
}
return 0;
}
Reference resources Algorithm learning notes (47): Binary heap
边栏推荐
- Function (error prone)
- English topic assignment (26)
- All in one 1413: determine base
- Error statuslogger log4j2 could not find a logging implementation
- 2022-2028 global and Chinese video coding and transcoding Market Research Report
- Raki's notes on reading paper: code and named entity recognition in stackoverflow
- Pointer function (basic)
- Construction d'un Cluster redis sous Windows
- 函数(易错)
- [groovy] closure (closure parameter binding | curry function | rcurry function | ncurry function | code example)
猜你喜欢
Key review route of probability theory and mathematical statistics examination
揭秘技术 Leader 必备的七大清奇脑回路
Flutter tips: various fancy nesting of listview and pageview
[Business Research Report] Research Report on male consumption trends in other economic times -- with download link
[groovy] closure (closure parameter binding | curry function | rcurry function | ncurry function | code example)
Cookie learning diary 1
Reading and visualization of DICOM, MHD and raw files in medical imaging
File upload bypass summary (upload labs 21 customs clearance tutorial attached)
质量体系建设之路的分分合合
The 22nd Spring Festival Gala, an immersive stage for the yuan universe to shine into reality
随机推荐
Stage experience
Neural network and deep learning Chapter 1: introduction reading questions
MacBook installation postgresql+postgis
Decimal to hexadecimal
Scope of package class package
Power management bus (pmbus)
JVM 原理和流程简介
概率论与数理统计考试重点复习路线
Setting up redis cluster cluster under Windows
Neural networks and deep learning Chapter 2: machine learning overview reading questions
自动语音识别(ASR)研究综述
Wenet: E2E speech recognition tool for industrial implementation
OWASP top 10 vulnerability Guide (2021)
[thingsboard] how to replace the homepage logo
直播预告 | 容器服务 ACK 弹性预测最佳实践
JMeter -- distributed pressure measurement
[groovy] closure (closure call is associated with call method | call () method is defined in interface | call () method is defined in class | code example)
可观测|时序数据降采样在Prometheus实践复盘
Flutter tips: various fancy nesting of listview and pageview
Managed service network: application architecture evolution in the cloud native Era