摘要：選擇問題概述從個數當中選出第個最大者。基本的堆操作見數據結構與算法分析用優先隊列解決選擇問題算法將個元素讀入數組，對數組應用算法。參考文獻數據結構與算法分析語言描述尋找最小的個數

從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