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

從N個(gè)數(shù)當(dāng)中選出第k個(gè)最大者。
最簡(jiǎn)單的兩種算法：

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

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

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

- 優(yōu)先隊(duì)列的簡(jiǎn)單實(shí)現(xiàn)

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

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

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

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

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

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

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

算法A4：
用簡(jiǎn)單方法A2，但用堆buildHeap來(lái)實(shí)現(xiàn)前k個(gè)數(shù),耗時(shí)O(k)-->檢測(cè)新元素是否進(jìn)入O(1)-->必要時(shí)刪除舊插入新O(logk)-->總時(shí)間O( k + (N - k)logk )=O( Nlogk )

算法A5：
選取S中一個(gè)元素作為樞紐元v，將集合S-{v}分割成S1和S2，就像快速排序那樣
如果k <= |S1|，那么第k個(gè)最小元素必然在S1中。在這種情況下，返回QuickSelect(S1, k)。
如果k = 1 + |S1|，那么樞紐元素就是第k個(gè)最小元素，即找到，直接返回它。
否則，這第k個(gè)最小元素就在S2中，即S2中的第（k - |S1| - 1）個(gè)最小元素，我們遞歸調(diào)用并返回QuickSelect(S2, k - |S1| - 1)。
此算法的平均運(yùn)行時(shí)間為O(N)。

在我自己的項(xiàng)目中，k=1或2.所以采用算法a2或者a4比較好。a2代碼量小，果斷采用。

[1]數(shù)據(jù)結(jié)構(gòu)與算法分析 java語(yǔ)言描述
[2]尋找最小的k個(gè)數(shù) http://taop.marchtea.com/02.01.html