训练1　第k大的数

题目描述（HDU4006）：小明和小宝正在玩数字游戏。游戏有n轮，小明在每轮游戏中都可以写一个数，或者询问小宝第k大的数是什么（第k大的数指有k-1个数比它大）。游戏格式：I c，表示小明写了一个数c；Q，表示小明询问第k大的数。请对小明的每次询问都给出第k大的数。

输入：输入多个测试用例。每个测试用例的第1行都为两个正整数n、k（1≤k≤n≤1 000 000），分别表示n轮游戏和第k大的数。然后是n行，格式为I c或Q。

输出：对于每次询问Q，都单行输出第k大的数。

提示：当写下的数的数量小于k时，小明不会询问小宝第k大的数是什么。

题解：本题数据量很大，直接求解或排序肯定超时，可以用优先队列解决。

1.算法设计

（1）用优先队列（最小值优先）存储最大的k个数。

（2）插入。插入元素c，若优先队列中的元素数量小于k，则c入队；否则若c大于队头元素，则队头元素出队，c入队。

（3）查询。查询第k大的数，直接输出队头元素即可。

2.完美图解

根据输入样例，操作过程如下。

（1）插入。I 1：元素数量小于3，1直接入队。I 2：元素数量小于3，2直接入队。I 3：元素数量小于3，3直接入队。优先队列的内部实现为堆，堆顶就是队头。

（2）查询。查询第3大的数，队头元素1为第3大的数。

（3）插入。I 5：元素数量不小于3，5比队头元素1大，队头元素1出队，5入队。

（4）查询。查询第3大的数，队头元素2为第3大的数。

（5）插入。I 4：元素数量不小于3，4比队头元素2大，队头元素2出队，4入队。

（6）查询。查询第3大的数，队头元素3为第3大的数。

3.算法实现