data-structures - 支持 LIFO 推送和弹出的优先队列？

Question

我需要设计一个具有以下约束的“优先队列堆栈”数据结构:

pop() 和 deleteMin() 在平均情况下以 O(log(n)) 运行。

push(x) 和 getMin() 的平均运行时间为 O(1)

有没有人有关于如何设计这个的建议？

Answer 1

您可以通过将标准堆栈与支持 O(1) 插入和 O(log n) 分摊删除的优先级队列组合在一起来实现这一点。例如，您可以将堆栈与斐波那契堆或偏斜二项式堆配对，两者都有这些保证。确保将指针存储在每个堆栈元素与其对应的优先级队列元素之间，以便在 O(1) 时间内您可以在两者之间跳转。

要压入一个元素，请将其压入堆栈并在 O(1) 时间内将其插入优先级队列。要读取最小值，请在 O(1) 时间内查询优先级队列以获取最小值。

要删除最小值，请从优先级队列中调用extract-min 删除最小值，然后进入堆栈并将删除的元素标记为无效。这需要 O(1) 时间。要弹出，重复弹出堆栈，直到弹出未标记为无效的元素，然后在优先级队列上调用 delete 以删除该元素。这需要时间 O(k + log n)，其中 k 是执行的弹出次数。但是，您可以使用潜在方法证明这是 O(1) 摊销的。如果将堆栈的潜在性设置为无效参数的数量，则每个 delete-min 将潜在性增加 1，并且每次弹出 k 个无效元素的 pop 操作将潜在性降低 k。因此，pop 的摊销运行时间为 O(log n)。

希望这有帮助!