此问题在此处已有答案：

Data structure (in STL or Boost) for retrieving kth smallest/largest item in a set?（1个答案）
6天前关闭
我正在寻找一个数据结构，存储在STL的整数。
我必须支持的主要操作是插入和删除，找到前20个元素，并找到任何k的第k个最大元素。
我知道有了一个set，我可以在log N时间内实现插入和删除，在O（1）时间内实现top 20，在O（k）时间内实现top k。
有没有办法选择一个数据结构，它可能有更好的能力找到前k个条目？例如，选择k = N/2-中位数--它需要O（N）时间使用一个集合，但理想情况下，我们可以有更好的东西。