數據結構中提取O（LGN）中位數和第二個最小元素

Question

我需要找到滿足這些要求的數據結構：

• 可以從n個項目中爲O（n）的列表構建它
• 插入項目需要O（LGN）
• 提取中位需要O（LGN）
• 提取第二最小項需要O（LGN）

對於第三個R這是有效的：將最小堆中的n/2個最小項和最小堆中最大的n/2個保留。那些堆的根將是低/高中位數。

但我堅持第四項要求。有任何想法嗎？

Answer 1

將n/2最大的物品放在最小的堆中。對於n/2個最小的項目，保持一對最大和最小堆。這對堆中的堆增加了配對堆中相同元素的索引，以便任何堆修改都更新所有移動項的配對堆中的索引。

配對堆解釋

兩個堆包含完全相同的一組項目。每個項目都有一個額外的索引字段。當堆被修改時，有些項目可能會改變它們的位置。如果項目從索引x移至索引y，則必須通知配對堆中的相應項目。這個相應的項目很容易位於與移動項目的索引字段配對的堆中。並且相應項目的索引字段的內容從x更改爲y。這允許所有堆項目準確地知道它們對的位置。保持兩個堆中的相應項目同步允許（從最大堆中提取最大項或從最小堆中提取第二個最小項）從配對堆中提取相應項。保持堆內同步不會增加任何複雜性要求。