摘要：選擇問題概述從個數(shù)當中選出第個最大者?；镜亩巡僮饕姅?shù)據(jù)結構與算法分析用優(yōu)先隊列解決選擇問題算法將個元素讀入數(shù)組，對數(shù)組應用算法。參考文獻數(shù)據(jù)結構與算法分析語言描述尋找最小的個數(shù)

從N個數(shù)當中選出第k個最大者。
最簡單的兩種算法：

算法A1：排序-->返回k位置的數(shù)。時間復雜度O(N^2)

算法A2：先讀入前k個數(shù)-->排序-->逐個讀入其余-->插入/丟掉。時間復雜度O(KN)
K=N/2 (上取整) 時，兩者復雜度都是O(N^2)

- 優(yōu)先隊列基本模型

- 優(yōu)先隊列的簡單實現(xiàn)

方法a,鏈表：表頭插入-->遍歷鏈表刪除最小元。時間復雜度O(1)+O(N)
方法b,二叉查找樹。時間復雜度O(logN)

- 優(yōu)先隊列更好的實現(xiàn)方案：二叉堆（簡稱堆）

a.二叉堆的結構性質
堆：完全填滿的二叉樹。底層元素從左到右填入。（完全二叉樹）
完全二叉樹，高h與節(jié)點數(shù)N的關系

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

完全二叉樹非常規(guī)律-->可以用數(shù)組表示完全二叉樹
位置i的元素-->左兒子[2i],右兒子（2i+1）,父親(i/2)下取整
b.堆序性質
堆序性質（heap-order property）：讓操作快速執(zhí)行的性質
在一個堆中，每一個子節(jié)點X的父親中的關鍵字小于等于X的關鍵字，根節(jié)點除外。
c.基本的堆操作（見數(shù)據(jù)結構與算法分析P153）

算法A3：
將N個元素讀入數(shù)組，對數(shù)組應用buildHeap算法。執(zhí)行k次deleteMin操作。

buildHeap最壞情況用時O(N)
每次deleteMin用時O(logN)
k次deleteMin-->用時O(klogN + N)

算法A4：
用簡單方法A2，但用堆buildHeap來實現(xiàn)前k個數(shù),耗時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]數(shù)據(jù)結構與算法分析 java語言描述
[2]尋找最小的k個數(shù) http://taop.marchtea.com/02.01.html