最小K个数（力扣面试题17.14）

本文采用的是大堆排序求最小的K个值。需要有堆的数据结构基础哦。

代码展示：

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void AdjustDown(int* parr,int n,int root)//向下调整
{
    int parent=root;
    int child = parent*2+1;
    while(child<n)
    {
        if(child+1<n&&parr[child+1]>parr[child]){
            child++;
        }
        if(parr[parent]<parr[child])
        {
            int tem=parr[parent];
            parr[parent]=parr[child];
            parr[child]=tem;

            parent=child;
            child=parent*2+1;
        }
        else
        {
            break;
        }
    }
}
int* smallestK(int* arr, int arrSize, int k, int* returnSize){
    
    if(k==0)
    {
        return NULL;
    }
    int* st=(int*)malloc(sizeof(int)*k);
    *returnSize=k;
    for(int i=0;i<k;i++)
    {
        st[i]=arr[i];
    }
    for(int i=(k-2)/2;i>=0;i--)//向下调整形成大堆，(k-2)/2是求父亲节点
    {
        AdjustDown(st,k,i);
    }
    for(int i=k;i<arrSize;i++)//如果数组元素小于堆顶元素，则代替堆顶元素，再形成新的大堆
    {
        if(arr[i]<st[0])
        {
            st[0]=arr[i];
            AdjustDown(st,k,0);
        }
    }
    return st;
}

 值得注意的是，已知孩子节点求父亲节点的公式是：parent=(child-1)/2。