查找最小的k个元素 （C语言代码）堆实现

解题思路:

用堆来解决这类问题十分合适。

如果直接将数组进行排序的话，显然不是很合理，因为可能会造成很大的浪费，比如要在10000个数中抽取1个数，而去大费周章把整个数组都给排了序，显然十分浪费电脑资源。因此只需要建个最小堆（小顶堆），让这个数组局部有序即可。

何为堆？

堆是一种特殊的二叉树，树的根的值是整棵树的最小值或者最大值（看这是棵什么树，小顶堆就是最小值），

左右子树也需要满足这一点，左子树的根是左子树中最大或者最小的，以此类推。

参考代码:

#include<stdio.h>

#include<malloc.h>

#include<limits.h>

void swap(int *a,int *b){

int temp=*a;

*a=*b;

*b=temp;

}

void PercUp(int* array,int size,int loc){//上滤 

int parent,child;

for(parent=loc;parent*2+1<size;parent=child){

child=parent*2+1;

if(child+1<size&&array[child]>array[child+1])

child++;//如果当前位置parent有两个孩子，找出值最小的那个孩子

if(array[parent]>array[child]){

//如果parent的值大于孩子的值，则将它调整为小顶堆 

swap(&array[parent],&array[child]);

}else{

//如果parent的值比孩子的值小，则已经是小顶堆 

return;

}

}

}

void buildMinHeap(int* array,int size){

for(int temp=size/2;temp>=0;temp--){

PercUp(array,size,temp);

}

}

void printMin(int *array,int size){

buildMinHeap(array,size);

printf("%d ",array[0]);

array[0]=INT_MAX;

}

int main(){

int size,num;

    scanf("%d%d",&size,&num);

int* array=(int*)malloc(size*sizeof(int));

for(int i=0;i<size;i++)

scanf("%d",&array[i]);

for(int i=0;i<num;i++)

printMin(array,size);

return 0;

}