按大小选择第K个数的问题（top-k选择问题）

摘要：选择问题概述从个数当中选出第个最大者。基本的堆操作见数据结构与算法分析用优先队列解决选择问题算法将个元素读入数组，对数组应用算法。参考文献数据结构与算法分析语言描述寻找最小的个数

从N个数当中选出第k个最大者。
最简单的两种算法：

算法A1：排序-->返回k位置的数。时间复杂度O(N^2)

算法A2：先读入前k个数-->排序-->逐个读入其余-->插入/丢掉。时间复杂度O(KN)
K=N/2 (上取整) 时，两者复杂度都是O(N^2)

- 优先队列基本模型

- 优先队列的简单实现

方法a,链表：表头插入-->遍历链表删除最小元。时间复杂度O(1)+O(N)
方法b,二叉查找树。时间复杂度O(logN)

- 优先队列更好的实现方案：二叉堆（简称堆）

a.二叉堆的结构性质
堆：完全填满的二叉树。底层元素从左到右填入。（完全二叉树）
完全二叉树，高h与节点数N的关系

N = 2^h ~ 2^(h+1) - 1
h = O(logN)

完全二叉树非常规律-->可以用数组表示完全二叉树
位置i的元素-->左儿子[2i],右儿子（2i+1）,父亲(i/2)下取整
b.堆序性质
堆序性质（heap-order property）：让操作快速执行的性质
在一个堆中，每一个子节点X的父亲中的关键字小于等于X的关键字，根节点除外。
c.基本的堆操作（见数据结构与算法分析P153）

算法A3：
将N个元素读入数组，对数组应用buildHeap算法。执行k次deleteMin操作。

buildHeap最坏情况用时O(N)
每次deleteMin用时O(logN)
k次deleteMin-->用时O(klogN + N)

算法A4：
用简单方法A2，但用堆buildHeap来实现前k个数,耗时O(k)-->检测新元素是否进入O(1)-->必要时删除旧插入新O(logk)-->总时间O( k + (N - k)logk )=O( Nlogk )

算法A5：
选取S中一个元素作为枢纽元v，将集合S-{v}分割成S1和S2，就像快速排序那样
如果k <= |S1|，那么第k个最小元素必然在S1中。在这种情况下，返回QuickSelect(S1, k)。
如果k = 1 + |S1|，那么枢纽元素就是第k个最小元素，即找到，直接返回它。
否则，这第k个最小元素就在S2中，即S2中的第（k - |S1| - 1）个最小元素，我们递归调用并返回QuickSelect(S2, k - |S1| - 1)。
此算法的平均运行时间为O(N)。

在我自己的项目中，k=1或2.所以采用算法a2或者a4比较好。a2代码量小，果断采用。

[1]数据结构与算法分析 java语言描述
[2]寻找最小的k个数 http://taop.marchtea.com/02.01.html