我需要设计一个具有以下约束的“优先队列堆栈”数据结构：
- pop() 和 deleteMin() 在平均情况下以 O(log(n)) 运行。
- push(x) 和 getMin() 平均运行时间为 O(1)
有人对如何设计这个有建议吗？
问问题
638 次
2 回答
3
您可以通过将标准堆栈与支持 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 都会将潜力增加一，并且每次弹出 k 个无效元素的弹出操作都会将潜力减少 k。因此，pop 的摊销运行时间为 O(log n)。
希望这可以帮助！
于 2013-01-16T17:18:48.853 回答
0
您可以将 Stack 与指向最小值对象一起使用。所以在这种情况下 push(x),pop(), getMin() 将在 O(1) 中 - 在平均时间内。
但是在 deleteMin() 之后，你需要调整顶部的项目。
于 2013-01-16T16:52:43.130 回答