IndexMinPQ的目的是Sedgwick和Wayne的算法4。

huangapple go评论85阅读模式
英文:

IndexMinPQ purpose algorithms 4 by Sedgwick and Wayne

问题

我对IndexMinPQ数据结构的用途不太清楚。这里提供了一个实现:IndexMinPQ.java

尽管书本本身提供了简要介绍,但仍不太清楚。我不太明白为什么我们需要这种数据结构以及其他操作?

英文:

I am not clear about the IndexMinPQ data structure purpose . An implementation is given IndexMinPQ.java .

Although book itself provide brief introduction but not clear . I am not clear why we needed this data structure and other operations?

答案1

得分: 2

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

索引优先队列维护了一个查找结构,以便你可以在 O(1) 的时间内找到节点。

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

英文:

The problem with heap implementation of a priority queue is that it's difficult to find a particular node. For example, suppose you have a heap with 100,000 items in it, and you want to decrease the priority of a node that has the value 732. The only way you can find that node is through a linear search of the heap. Decreasing the priority of the node is an O(log n) operation, but finding the node is O(n).

An indexed priority queue maintains a lookup structure so that you can find the node in O(1).

This ability is important in any system that needs to modify nodes in a priority queue. A job scheduler, for example, in which you frequently need to adjust the priority of jobs, or cancel jobs.

huangapple
  • 本文由 发表于 2020年4月10日 09:00:58
  • 转载请务必保留本文链接:https://go.coder-hub.com/61132540.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定