在O(lgn)中提取中值和第二个最小元素的数据结构

Question

我需要找到满足这些要求的数据结构:

• 可以从O(n)中的n个项目列表构建它
• 插入一个项目需要O(lgn)
• 提取中位数需要O(lgn)
• 提取第二个最小项目需要O(lgn)

对于前三个要求,这是有效的:将最多堆中的n/2个最小项保持为最小堆中的n/2个最小项.这些堆的根将是下/上中位数.

但我坚持第四个要求.有任何想法吗？

Answer 1

将 n/2 最大的项保留在最小堆中。对于 n/2 个最小的项，维护一对最大堆和最小堆。该对中的堆会使用配对堆中相同元素的索引进行扩充，以便任何堆修改都会更新配对堆中所有移动项的索引。

配对堆解释

两个堆都包含完全相同的一组项目。每个项目都有一个附加的索引字段。当堆被修改时，某些项目可能会改变它们的位置。如果一个项目从一个索引移动x到另一个索引y，则必须通知配对堆中的相应项目。这个对应的项目很容易在带有移动项目索引字段的成对堆中找到。并且对应项的索引字段的内容由x变为y。这使得所有堆项目都可以准确地知道它们对的位置。保持两个堆中的相应项目同步允许（同时从最大堆中提取最大的项目或从最小堆中提取第二小的项目）从配对堆中提取相应的项目。并且保持堆同步不会增加任何复杂性要求。