力扣（LeetCode）----前k个最小数
1 题目描述
设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
示例：
输入： arr = [1,3,5,7,2,4,6,8], k = 4
输出： [1,2,3,4]提示：
0 <= len(arr) <= 100000
0 <= k <= min(100000, len(arr))
这个题如果用普通的排序操作其实很简单，直接用冒泡把所有数字从小到大排序就行，但如果数据量很大呢，大到内存存不下的话，就会导致冒泡这类排序的时间复杂度太大导致无法实现。
这时我们就需要利用到堆。
2 解题思路
假如给了一个N个元素大的数组，需要去取得这个数组里面的前5个最小的数。
这时候我们可以将arr内前五个元素取出来去建立一个大堆，因为要取前几个最小的数，所以我们建一个大根堆。
通过循环向下调整算法去将它调整为大根堆。
void AdjustDown(int *a,int k,int root)
{int parent=root;int child=parent*2+1;while(child<k){if(child+1<k&&a[child]<a[child+1]){child++;}if(a[child]>a[parent]){int temp=a[parent];a[parent]=a[child];a[child]=temp;parent=child;child=parent*2+1;}else{break;}}
}
然后再将数组中后面没用来建堆的数来和大堆的头去比较，小于堆顶的直接入堆。
然后在进行向下调整。
这样我们就把小的数字放到最下面，重复这个步骤就能把这N个最小的数字给放到这个堆里面去。
3 完整代码
/*** Note: The returned array must be malloced, assume caller calls free().*/void AdjustDown(int *a,int k,int root)
{int parent=root;int child=parent*2+1;while(child<k){if(child+1<k&&a[child]<a[child+1]){child++;}if(a[child]>a[parent]){int temp=a[parent];a[parent]=a[child];a[child]=temp;parent=child;child=parent*2+1;}else{break;}}
}int* smallestK(int* arr, int arrSize, int k, int* returnSize){*returnSize=k;if(k==0) return NULL;int *a=(int*)malloc(sizeof(int)*k);memcpy(a,arr,sizeof(int)*k);for(int i=(k-1-1)/2;i>=0;i--){AdjustDown(a,k,i);}for(int i=k;i<arrSize;i++){if(a[0]>arr[i]){a[0]=arr[i];AdjustDown(a,k,0);}}return a;
}