c++ - O(1) 中的 extractMin 操作使用 2 个堆栈

Question

给定一个连续的整数流和两个堆栈。我想实现以 O(1) 复杂度运行的 extractMin 操作。此操作从记录中弹出最小元素并将其返回。基本解决方案是使用 2 个堆栈以反向排序顺序保存数据。这样我们就可以简单地弹出包含数据的栈顶元素。但是有了这个，每个整数的插入都是 O(N) 。我能否在插入时获得更好的复杂性，同时将 extractMin 操作保持为 O(1)。

添加示例以使其更清楚:

10,-2​​0,2,-3,-5,10,20(任意时刻的整数流)。

extractMin() // returns -20
extractMin() // returns -5

Answer 1

您无法使用堆栈获得更好的复杂性。即使您要求使用堆栈进行常量提取，问题的措辞似乎也没有明确禁止使用其他数据结构。

在我的回答的早期版本中，我建议最小堆，它在整个堆的构建过程中平均插入恒定(在最坏的情况下，单个插入是对数的)。然而，堆不允许持续提取，而只能进行对数提取。

要对多个值进行持续提取，您需要对所有值进行排序。以比堆栈更复杂的方式实现这一点的一种方法是构建二叉搜索树，同时跟踪最小节点。使用平衡 bst，可以实现对数插入。为了获得恒定的个体提取，您还需要在每个节点中存储一个父指针。但是，如果您只需要按顺序遍历所有值，则不需要指针。