Sedgwick 和 Wayne 的 IndexMinPQ 目的算法 4

Question

我不清楚 IndexMinPQ 数据结构的用途。给出了一个实现 IndexMinPQ.java .

虽然书本身有简单的介绍但不是很清楚。我不清楚为什么我们需要这个数据结构和其他操作？

Answer 1

优先级队列的堆实现的问题是很难找到特定的节点。例如，假设您有一个包含 100,000 个项目的堆，并且您想要降低值为 732 的节点的优先级。找到该节点的唯一方法是通过对堆进行线性搜索。降低节点的优先级是一个 O(log n) 操作，但是 找到 节点是 O(n).

索引优先级队列维护一个查找结构，以便您可以在 O(1) 中找到节点。

这种能力对于任何需要修改优先级队列中的节点的系统都很重要。作业调度程序，例如，您经常需要在其中调整作业的优先级或取消作业。