数据结构网络化用于获取

Question

我试图解决万阿英，蒋达清第k值最大的种种疑问的规定：使支持数据结构：

1）添加元素与密钥K

2）删除与密钥k元

3）打印数据结构第k最大元素

我认为maxheap应该工作，但在这种情况下，我们需要删除堆前k-1最大的价值，以获得第k个最大的元素，所以它赢得在这里工作。

我该如何解决这个问题？

Answer 1

你可以用一个order statistic tree来解决这个问题，它是一个（平衡）二叉树，可以让你在log（n）时间内用平衡树找到第i个最小（或最大）元素。