算法：最小的k个数

数据结构和算法

可以先排序在取，但是速度慢

三种方法

O(n)，但是修改了数组

基于Partition，第k小的在左边

O(n)，也修改了数组

堆排序

O(nlogK)，适合海量数据

创建大小为k的容器存储最小的k个数字
读入一个数字，如果已有的数字都小于k个，则直接放入容器，如果已经有k个数字，则找出K个中最大值，然后拿这次待插入的整数和最大值比较，如果带插入的值比现有的最大值小，则替换，否则不是最小的k个整数之1，抛弃这个整数

容器实现方式：3个
可以用二叉树实现这个容器，能够在O(logk)时间内实现3步：找到最大值，可能删除最大数，可能插入新数字
对n个数字，总的时间效率是O(nlogk)

也可以使用最大堆找到k个最大数，可以在O（1）内找到已有的k个数字的最大值，但插入删除需要O(logk)
也可以使用红黑树：O（logk）内完成查找删除插入