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

Question

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

可以从 O(n)

中的 n 个项目的列表中构建它

插入一个项目需要 O(lgn)

提取中位数需要 O(lgn)

提取第二小的项目需要 O(lgn)

对于前三个要求，这是有效的:在最大堆中保留 n/2 个最小的项目，在最小堆中保留 n/2 个最大的项目。这些堆的根将是较低/较高的中位数。

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

Answer 1

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

成对堆解释

两个堆都包含完全相同的项目集。每个项目都有一个额外的索引字段。当堆被修改时，一些项目可能会改变它们的位置。如果一个项目从索引 x 移动到索引 y ，必须通知配对堆中的相应项。这个对应的项目很容易在成对的堆中与移动项目的索引字段一起定位。并且对应item的index字段的内容由x改变至 y .这允许所有堆项目准确地知道它们的对所在的位置。保持两个堆中的相应项同步允许(同时从最大堆中提取最大项或从最小堆中提取第二个最小项)从配对堆中提取相应项。并且保持堆同步不会增加任何复杂性要求。