【题目】
输入n个整数，输出当中最小的k个。
比如输入1，2。3。4，5，6。7和8这8个数字，则最小的4个数字为1，2。3和4。
【分析】
这道题最简单的思路莫过于把输入的n个整数排序，这样排在最前面的k个数就是最小的k个数。仅仅是这样的思路的时间复杂度为O(nlogn)。
我们试着寻找更快的解决思路。
我们能够先创建一个大小为k的数据容器来存储最小的k个数字。
接下来我们每次从输入的n个整数中读入一个数。
假设容器中已有的数字少于k个，则直接把这次读入的整数放入容器之中。假设容器中已有k个数字了。也就是容器已满，此时我们不能再插入新的数字而仅仅能替换已有的数字。我们找出这已有的k个数中最大值，然和拿这次待插入的整数和这个最大值进行比較。假设待插入的值比当前已有的最大值小，则用这个数替换替换当前已有的最大值；假设带插入的值比当前已有的最大值还要大，那么这个数不可能是最小的k个整数之中的一个，由于我们容器内已经有k个数字比它小了。于是我们能够抛弃这个整数。
因此当容器满了之后。我们要做三件事情：一是在k个整数中找到最大数。二是有可能在这个容器中删除最大数，三是可能要插入一个新的数字。并保证k个整数依旧是排序的。假设我们用一个二叉树来实现这个数据容器，那么我们能在O(logk)时间内实现这三步操作。
因此对于n个输入数字而言，总的时间效率就是O(nlogk)。
我们能够选择用不同的二叉树来实现这个数据容器。因为我们每次都须要找到k个整数中的最大数字，我们非常easy想到用最大堆。在最大堆中。根结点的值总是大于它的子树中随意结点的值。于是我们每次能够在O(1)得到已有的k个数字中的最大值，但须要O(logk)时间完毕删除以及插入操作。
我们自己能够实现一个最大堆。
我们还能够採用红黑树来实现我们的容器。红黑树通过把结点分为红、黑两种颜色并依据一些规则确保树是平衡的，从而保证在红黑树中查找、删除和插入操作都仅仅须要O(logk)。在STL中set和multiset都是基于红黑树实现的。
假设面试官不反对我们用STL中的数据容器。
【代码】
/*********************************
* 日期：2013-12-18
* 作者：SJF0115
* 题目: 5.查找最小的k个元素
* 来源：
* 分类：程序猿面试题精选100题
**********************************/
#include <iostream>
using namespace std;
//调整以index为根的子树
//n：堆中元素个数
void MaxHeap(int a[],int index,int n){
if(n < 2){
return;
}
int largestIndex = index;
// 左子节点下标
int leftIndex = 2 * index;
// 右子节点下标
int rightIndex = 2 * index + 1;
// 左子节点最大
if(leftIndex <= n && a[leftIndex] > a[largestIndex]){
largestIndex = leftIndex;
}//if
// 右子节点最大
if(rightIndex <= n && a[rightIndex] > a[largestIndex]){
largestIndex = rightIndex;
}//if
//假设a[index]是最大的，则以index为根的子树已是最大堆否则index的子节点有最大元素
//则交换a[index],a[LargetIndex],从而使index及子女满足堆性质
int temp;
if(largestIndex != index){
// 交换
temp = a[largestIndex];
a[largestIndex] = a[index];
a[index] = temp;
//又一次调整以LargestIndex为根的子树
MaxHeap(a,largestIndex,n);
}//if
}
//建堆：将一个数组a[1-n]变成一个最大堆
void BuildMaxHeap(int a[],int n){
//子数组a[(n/2+1,n/2+2......n)]中的元素都是树中的叶子不用调整
for(int i = n/2;i >= 1;i--){
// 调整以i为根节点的树使之成为最大堆
MaxHeap(a,i,n);
}
}
//堆排序
void HeapSort(int*& a,int n){
int tmp;
//数组中最大元素在根a[1]。则能够通过它与a[i]交换来达到终于的正确位置
for(int i = n;i > 1;i--){
// 交换
tmp = a[i];
a[i] = a[1];
a[1] = tmp;
//a[i]已达到正确位置，从堆中去掉
n--;
//又一次调整
MaxHeap(a,1,n);
}
}
// 最小K个数
void MinK(int a[],int k,int n){
for(int i = k+1;i <= n;i++){
//假设X比堆顶元素Y大，则不须要改变原来的堆
//假设X比堆顶元素Y小。那么用X替换堆顶元素Y。
//在替换之后。X可能破坏了最大堆的结构，须要调整堆来维持堆的性质
int temp;
if(a[i] < a[1]){
temp = a[i];
a[i] = a[1];
a[1] = temp;
// 又一次调整最大堆
MaxHeap(a,1,k);
}
}
// 堆排序
HeapSort(a,k);
// 输出
for(int i = 1;i <= k;i++){
cout<<a[i]<<endl;
}
}
int main(){
int k = 5;
//a[0]不用。堆的根结点是从1開始的
int a[] = {0,3,17,8,27,7,20,5,35,6};
//BulidMaxHeap将输入数组构造一个最大堆
BuildMaxHeap(a,k);
// 最小k个元素
MinK(a,k,9);
return 0;
}
參考： 堆排序