一个关于堆的问题
假设有个黑盒子，初始为空。我们有两种操作，ADD(i) 和 GET(i)。ADD(i) 是把整数 i 放入黑盒中。GET(i) 是返回黑盒子中第 i 小的值，满足 GET(i) 时黑盒中的整数个数 n > = i。
现在给定一组操作，要求返回顺次给出所有 GET 操作的结果。如下例：
操作 结果
ADD(3)
GET(1) 3
ADD(1)
GET(2) 3
ADD(-4)
ADD(2)
ADD(8)
ADD(-1000)
GET(3) 1
GET(4) 2
ADD(2)
直接的想法，在 ADD 操作时对已给出的数据进行插入排序，GET 时返回下标对应的值。但这样的话时间复杂度为 O(N^2)。
有更好的算法么？
有人说用堆，但我想不出堆在这种情况下怎么用。
[解决办法]
用堆是很好的方法。可以参考《算法导论》
另外你是取第i小的值，可能要做一些扩展，比如节点保存子树的节点总数。
ADD和GET都是Olgn的复杂度。
你的算法ADD是O(n),不是O(n^2)
[解决办法]
原题的GET的描述与楼主的略有出入.
请见原题: http://acm.zju.edu.cn/show_problem.php?pid=1319
注意GET的描述的不同.
对于原题, 用堆的做法, 是一个大根堆顶配合一个小根堆, 保证每次GET的操作复杂度是O(1), ADD是O(logN).
如果不是原题的GET的要求, 而是楼主的GET(i), 其实用个平衡二叉树也可以做到GET是O(logN)的, ADD是O(logN)的.
