概括查找分钟/查找 - 最大堆栈任意顺序统计？ [英] Generalizing the find-min/find-max stack to arbitrary order statistics?

问题描述

在 这个前面的问题 的OP要求类似于堆栈的数据结构支持以下操作在O（1）每次：

In this earlier question, the OP asked for a data structure similar to a stack supporting the following operations in O(1) time each:

• 一键，还增加了一个新的元素堆顶上，
• 流行，这从栈中删除顶部的元素，
• 找到-Max的，它返回（但不删除）堆栈的最大元素，而
• 找到民，返回（但不删除）堆栈的最小元素。

几分钟前，我发现的 此相关的问题 要求澄清上的类似要查询的数据结构，而不是允许的最大和最小要查询的是，允许对堆的中位数元素。这两个数据结构似乎是更一般的数据结构的一种特殊情况，支持以下操作：

A few minutes ago I found this related question asking for a clarification on a similar data structure that instead of allowing for the max and min to be queried, allows for the median element of the stack to be queried. These two data structures seem to be a special case of a more general data structure supporting the following operations:

• 在推，这将元素堆栈之上，
• 流行音乐，该弹出堆栈的顶部，和
• 找到-K个，其中为创建结构时确定的固定氏/ STRONG>，返回的第k最大堆栈的元素。

有可能通过存储栈和平衡的二叉搜索树拿着顶k个元素，这将使所有这些操作运行在O支持所有这些操作（日志K）的时间。我的问题是这样的：是有可能实现上述数据结构比这更快也就是说，可以得到O（1）所有三种操作？或许O（1）push和pop和O（日志k）为顺序统计查询？

It is possible to support all of these operations by storing a stack and an balanced binary search tree holding the top k elements, which would enable all these operations to run in O(log k) time. My question is this: is it possible to implement the above data structure faster than this? That is, could we get O(1) for all three operations? Or perhaps O(1) for push and pop and O(log k) for the order statistic lookup?

推荐答案

由于结构可用于k个元素为O（k）的推排序并找到-k个操作，每基于比较的实现有，它们中的至少一个成本欧米茄（日志K），即使在摊销感，搭配随机化。

Since the structure can be used to sort k elements with O(k) push and find-kth operations, every comparison-based implementation has at least one of these cost Omega(log k), even in an amortized sense, with randomization.

一键即可为O（log k）和流行/发现，第k可以是O（1）（使用持久性数据结构;推进应该precompute的顺序统计）。我基于与比较的算法下界工作的直觉是，O（1）推/ POP和O（日志K）发现，第k是可行的，但需要摊销。

Push can be O(log k) and pop/find-kth can be O(1) (use persistent data structures; push should precompute the order statistic). My gut feeling based on working with lower bounds for comparison-based algorithms is that O(1) push/pop and O(log k) find-kth is doable but requires amortization.

这篇关于概括查找分钟/查找 - 最大堆栈任意顺序统计？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！