题解 | #找到无序数组中最小的k个数#

//本题用一个大小为k的大根堆即可解决
//遍历arr数组的每一个数，如果此时大根堆还没满就直接放入堆中，否则和大根堆的堆顶比较
//如果比堆顶要小则替换堆顶再重新调整成大根堆
//最后大根堆中的k个数就是数组中最小的k个数
#include<bits/stdc++.h>
using namespace std;
void heapInsert(int *heapArray,int data,int &heapSize);//建大根堆的函数
void heapfi(int *heapArray,int &heapSize);//重新调整成大根堆的函数
int main(){
    int n,k;
    cin>>n>>k;
    int *arr=new int[n];
    int *heapArray=new int[k];
    int heapSize=0;//限制堆的大小
    for(int i=0;i<n;i++){
        cin>>arr[i];
        //调整堆
        if(heapSize<k){
            heapInsert(heapArray, arr[i], heapSize);
        }
        else{//堆里面已经放满了，此时arr[i]如果比堆顶的值要小就交换堆顶的值，并重新调整堆
            if(arr[i]<heapArray[0]){
                heapArray[0]=arr[i];
                heapfi(heapArray, heapSize);
            }
            else continue;
        }
    }
    //最后大根堆里的k个数就是最小的k个数
    for(int i=0;i<k;i++){
        cout<<heapArray[i]<<" ";
    }
    delete []arr,heapArray;
    return 0;
}
void heapInsert(int *heapArray,int data,int &heapSize)
{
    heapArray[heapSize++]=data;//先将这个数放入大根堆中
    //然后向上调整成大根堆,即和自己的父亲节点的值相比
    int pos=heapSize-1;
    while(heapArray[pos]>heapArray[(pos-1)/2]){//比他的父亲的值还要大，交换
        int temp=heapArray[pos];
        heapArray[pos]=heapArray[(pos-1)/2];
        heapArray[(pos-1)/2]=temp;
        pos=(pos-1)/2;//继续向上
    }
}
//堆顶的值被替换成新的值了
//重新调整成大根堆
void heapfi(int *heapArray,int &heapSize)
{
    int pos=0;
    while(2*pos+1<heapSize){//当还有左孩子时
        int max=2*pos+2>=heapSize||heapArray[2*pos+1]>heapArray[2*pos+2]?2*pos+1:2*pos+2;
        if(heapArray[max]>heapArray[pos]){//孩子比父亲大
            int temp=heapArray[max];
            heapArray[max]=heapArray[pos];
            heapArray[pos]=temp;
            pos=max;//向下移动
        }
        else break;
    }
}