我需要设计一个具有以下约束的“优先级队列堆栈”数据结构:
- 一般情况下，pop() 和 deleteMin() 的运行时间复杂度为 O(log(n))。
- push(x) 和 getMin() 的平均运行时间为 O(1)
有人对如何设计这个有什么建议吗？
最佳答案
您可以通过将标准堆栈与支持 O(1) 插入和 O(log n) 分摊删除的优先级队列组合在一起来实现此目的。例如，您可以将堆栈与斐波那契堆或倾斜二项式堆配对，两者都有这些保证。确保存储每个堆栈元素及其相应优先级队列元素的指针，以便在 O(1) 时间内可以在两者之间跳转。
要压入一个元素，请将其压入堆栈并在 O(1) 时间内将其插入优先级队列。要读取最小值，请在 O(1) 时间内查询优先级队列以获取最小值。
要删除最小值，请从优先级队列中调用 extract-min 删除最小值，然后进入堆栈并将删除的元素标记为无效。这需要 O(1) 时间。要弹出，请重复弹出堆栈，直到弹出未标记为无效的元素，然后在优先级队列上调用删除以删除该元素。这需要时间 O(k + log n)，其中 k 是执行的弹出次数。但是，您可以使用势方法证明这是摊销的 O(1)。如果将堆栈的潜力设置为无效参数的数量，则每个删除分钟都会将潜力增加 1，而弹出 k 个无效元素的每个弹出操作都会将潜力减少 k。因此，pop 的摊销运行时间为 O(log n)。
希望这有帮助!
关于data-structures - 支持 LIFO 压入和弹出的优先级队列？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/14363319/