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

解题思路:

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

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

何为堆？

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

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

参考代码:

#include<cstdio>
#include<malloc.h>
#include<limits.h>
using namespace std;
void swap(int &a,int &b){
    int temp=a;
    a=b;
    b=temp;
}
void PercDown(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--){
        PercDown(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;
}