algorithm - 获取第 k 个最大值的许多查询的数据结构

Question

我正在尝试解决以下问题:制作支持的数据结构:

1) 添加键为k的元素

2) 删除键为k的元素

3) 打印数据结构中第k大的元素

我认为 maxheap 应该可以工作，但在这种情况下我们需要从堆中删除第 k-1 个最大值以获得第 k 个最大元素，所以它在这里不起作用。

我该如何解决？

Answer 1

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