在线求n个数中第k大的，可否直接调用STL？该怎么处理
在线求n个数中第k大的，可否直接调用STL？
给定n个数，会动态的增加、删除、更改某个元素。也会随时询问当前第k大的数（每次的k不相等）。要求时间复杂度均为O(lg n)
一直想用set，但不知道怎么能做到。问了别人，有人让我手写set。实在是懒啊。。。STL真的没有解决方案吗？
------解决方案--------------------
最懒的做法是两个优先队列，一个保存K个数，另一个保存n-k。如果你足够聪明，应该懂我说什么了。手机打字少。
------解决方案--------------------
两种方法，效率不同，先说低的
1)先来个排序，随便哪种都行，heap sort，quick sort or merge sort，开销是n*log(n)，然后直
接取第k个元素就行了。
2)第二种是用分治法解决，类似于像随机快速排序里面的思想，开销O(n)。假如有1到n个数字，先任意选
择一个主元，将数列分成两个部分，假设主元的下标是p，所有小于主元的放在左侧，大于主元的放在右侧。
这一遍跑完了，n个数就分成了三组：(1,p-1),p,(p+1,n)，最左面的部分是小于主元的，中间是主元(可
能有多个和主元相等的值)，右侧是大于主元的。然后开始看三部分的长度，和要找的k比较，就知道要找的
那个元素会落在哪个区域里面了。然后继续用新的下标递归。
我的描述可能看不懂，具体的可以参阅《算法导论》第三版的9.2 Selection in expected linear time.
------解决方案--------------------
楼主。。可以用binary tree来实现。
每一个node里面添加2个数据：int left_count; int right_count；记录多少个node在这个node左边，和多少个node在这个node右边。
就可以log(n)的找到kth element。
------解决方案--------------------
我想了一下，我说的方法，
建立树 O(nlg n)
其他都是O(lg n)
可以用红黑树等复杂的树实现，必要时旋转一下。旋转的时候count处理要处理好。。
------解决方案--------------------
stl里指定没有，我说的二叉树方法可以用，自己实现一个也花不了1天，你这都耽搁了好几天了。
给定n个数，会动态的增加、删除、更改某个元素。也会随时询问当前第k大的数（每次的k不相等）。要求时间复杂度均为O(lg n)
一直想用set，但不知道怎么能做到。问了别人，有人让我手写set。实在是懒啊。。。STL真的没有解决方案吗？
------解决方案--------------------
最懒的做法是两个优先队列，一个保存K个数，另一个保存n-k。如果你足够聪明，应该懂我说什么了。手机打字少。
------解决方案--------------------
两种方法，效率不同，先说低的
1)先来个排序，随便哪种都行，heap sort，quick sort or merge sort，开销是n*log(n)，然后直
接取第k个元素就行了。
2)第二种是用分治法解决，类似于像随机快速排序里面的思想，开销O(n)。假如有1到n个数字，先任意选
择一个主元，将数列分成两个部分，假设主元的下标是p，所有小于主元的放在左侧，大于主元的放在右侧。
这一遍跑完了，n个数就分成了三组：(1,p-1),p,(p+1,n)，最左面的部分是小于主元的，中间是主元(可
能有多个和主元相等的值)，右侧是大于主元的。然后开始看三部分的长度，和要找的k比较，就知道要找的
那个元素会落在哪个区域里面了。然后继续用新的下标递归。
我的描述可能看不懂，具体的可以参阅《算法导论》第三版的9.2 Selection in expected linear time.
------解决方案--------------------
楼主。。可以用binary tree来实现。
每一个node里面添加2个数据：int left_count; int right_count；记录多少个node在这个node左边，和多少个node在这个node右边。
就可以log(n)的找到kth element。
------解决方案--------------------
我想了一下，我说的方法，
建立树 O(nlg n)
其他都是O(lg n)
可以用红黑树等复杂的树实现，必要时旋转一下。旋转的时候count处理要处理好。。
------解决方案--------------------
stl里指定没有，我说的二叉树方法可以用，自己实现一个也花不了1天，你这都耽搁了好几天了。