AcWing 838. 堆排序(c语言)
原题链接
简单
作者:
chengxi
,
2022-05-10 09:18:31
,
所有人可见
,
阅读 199
//首先每次都冲数组中取出一个数放到堆中,待所有数全部取完,便形成小根堆,因为是升序,每次取出一个最小值;
#include <stdio.h>
#include <stdlib.h>
#define N 100005
int heap[N];
int array[N];///存储已排序的元素
int len=0;
void swap(int *first,int *second){
int temp=*first;
*first=*second;
*second=temp;
}
void put_MinHeap(int num){//每次往堆里插入一个数并保证堆的性质
heap[++len]=num;///首先将要插入的元素放到,堆尾;
int now=len,next;//now指向当前的队尾
while(now>1){//如果now所指的元素大于堆顶的编号时;
next=now/2;//找到父节点;
if(heap[next]<=heap[now])break;
swap(&heap[next],&heap[now]);
now=next;///now指向当前以交换的结点
}
}
void get_(int k){//每次取出堆顶的元素,并形成新的小根堆
if(k<=0)
return;
int res=heap[1];
heap[1]=heap[len--];
int now=1,next;
while(now*2<len){///当所取得左子节点得下标不超过数组得长度时,循环
next=now*2;//取得当前结点得左子节点得值
if(heap[next]>heap[next+1])next++;
if(heap[next]>=heap[now])break;
swap(&heap[next],&heap[now]);
now=next;//now指向当前以交换得子节点
}
printf("%d ",res);
get_(k-1);
}
int main(void){
int n,m,i=0,k;
scanf("%d %d",&n,&m);
while(++i<=n){
scanf("%d",&k);
put_MinHeap(k);
}
get_(m);
return 0;
}