java - IndexMinPQ 目的算法 4 由 Sedgwick 和 Wayne 编写

Question

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

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

Answer 1

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

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

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