将find-min/find-max堆栈推广到任意顺序统计？

Question

在之前的这个问题中,OP要求一个类似于堆栈的数据结构,在每个O(1)时间内支持以下操作:

• 推送,在堆栈顶部添加一个新元素,
• Pop,从堆栈中删除顶部元素,
• Find-Max,返回(但不删除)堆栈的最大元素,和
• Find-Min,返回(但不删除)堆栈的最小元素.

几分钟前,我发现这个相关的问题要求澄清一个类似的数据结构,而不是允许查​​询最大值和最小值,允许查询堆栈的中值元素.这两个数据结构似乎是支持以下操作的更通用数据结构的特例:

• 推送,将元素推到堆栈顶部,
• 弹出,弹出堆栈的顶部,和
• Find-Kth,对于在创建结构时确定的固定k,返回堆栈的第k个最大元素.

通过存储堆栈和保存前k个元素的平衡二叉搜索树,可以支持所有这些操作,这将使所有这些操作在O(log k)时间内运行.我的问题是:是否有可能比这更快地实现上述数据结构？也就是说,我们可以为所有三个操作获得O(1)吗？或者也许O(1)用于推送和弹出,O(log k)用于订单统计查找？

Answer 1

由于该结构可用于使用O(k)push和find-kth操作对k个元素进行排序,因此每个基于比较的实现具有至少一个这样的成本Omega(log k),即使在摊销意义上,也具有随机化.

推送可以是O(log k),pop/find-kth可以是O(1)(使用持久数据结构;推送应该预先计算订单统计数据).基于比较算法的下限工作,我的直觉是O(1)push/pop和O(log k)find-kth是可行的,但需要摊销.