训练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. 算法实现