訓練1　第k大的數

題目描述（HDU4006）：小明和小寶正在玩數字游戲。游戲有n輪，小明在每輪中都可以寫一個數，或者問小寶第k大的數是什么（第k大的數指有k-1個數比它大）。游戲格式為：I c，表示小明寫下一個數c；Q，表示小明問第k大的數。請對小明的每個詢問都給出第k大的數。

輸入：輸入包含多個測試用例。每個測試用例的第1行都包含兩個正整數n、k（1≤k≤n≤1000000），表示n輪游戲和第k大的數。然后是n行，格式為I c或Q。

輸出：對每個詢問Q，都單行輸出第k大的數。

提示：當寫下的數字個數小于k個時，小明不會問小寶第k大的數。

題解：本題數據范圍很大，直接暴力肯定超時，因此可以借助優先隊列實現。

1. 算法設計

（1）使用優先隊列（最小值優先）存儲最大的k個數。

（2）插入。若隊中元素個數小于k，則直接入隊；若當前輸入元素大于隊頭，則隊頭出隊，當前元素入隊。

（3）查詢。隊頭（堆頂）就是第k大的數，輸出即可。

2. 完美圖解

根據輸入樣例，操作過程如下。

（1）插入。I 1：元素個數小于3，直接入隊。I 2：元素個數小于3，直接入隊。I 3：元素個數小于3，直接入隊。

（2）查詢。查詢第3大的數，隊頭1為第3大的數。數字3是第1大。

（3）插入。I 5：元素個數不小于3，5比隊頭大，則隊頭出隊，5入隊。

（4）查詢。查詢第3大的數，隊頭2為第3大的數。

（5）插入。I 4：元素個數不小于3，4比隊頭大，則隊頭出隊，4入隊。

（6）查詢。查詢第3大的數，隊頭3為第3大的數。

3. 算法實現