问题标签 [priority-queue]

我有一些对象的priority_queue：

有时，其中一个对象的优先级可能会发生变化 - 我需要能够以有效的方式更新队列中该对象的优先级。目前我正在使用这种有效但似乎效率低下的方法：

我以这种方式实现它是因为当时我有点着急，这是我能做的最快的事情，我可以肯定它会正常工作。不过，必须有比这更好的方法。我真正想要的是一种方法：

• 提取具有更改优先级的实例并插入具有新优先级值的新实例
• 使用更改的优先级更新实例，然后更新队列以使其正确排序

做这个的最好方式是什么？

我想将 java 的 PriorityQueue 类包装在 clojure 中，以便在我的程序的另一部分中使用。我想弄清楚的是，是否有任何方法可以以 lispy 的方式执行此操作并使优先级队列不可变。有什么好的方法可以做到这一点，或者我只是将 PriorityQueue 用作可变数据结构会更好？

如何对PriorityQueue我想要排序的内容进行排序？

offer另外，和add方法之间有区别吗？

请注意，我不是在寻求答案。我只是好奇为什么事情会奏效

我需要为班级分配的打印机模拟器实现优先级队列。在查看互联网上的示例后，我注意到 operator< 被超载以正确安排优先级队列。

有问题的代码：java2s 优先队列示例

为什么 operator< 需要重载？'<' 甚至在哪里进行比较？实现运算符重载会改变队列 STL 的工作方式吗？

这个实现对我来说似乎并不直观：为什么 operator> 没有被重载呢？应该如何知道 operator< 需要重载才能让 priority_queue 正常工作？

一旦 PriorityQueue 中对象的优先级发生变化，Java 是否有一种简单的方法来重新评估堆？我在 中找不到任何迹象Javadoc，但必须有办法以某种方式做到这一点，对吧？我目前正在删除该对象，然后重新添加它，但这显然比在堆上运行更新要慢。

对于我的 CS 类，我需要在 Java 中实现 Prim 算法，并且我在优先级队列步骤中遇到问题。我有优先级队列的经验，并且了解它们通常可以工作，但我在某个特定步骤时遇到了麻烦。

我创建了一个包含键值（我假设它是连接到节点的最轻的边缘）和父节点的节点类。我的问题是我不明白将节点添加到优先级队列中。当父节点设置为 NIL 并将键设置为 ∞ 时，将所有节点添加到优先级队列对我来说没有意义。

I have a class that I would like to use in a scala.collection.mutable.PriorityQueue, but I don't want to make it Ordered[A] just for this one purpose. I don't consider the ordering I want to use with respect to the PriorityQueue as the natural ordering of the class.

So, in my PriorityQueue, I would like the values to be ordered by 'sequence'. However, just because two objects have the same sequence doesn't make them naturally equal since the contents of their 'values' may be different.

This is where, in Java, it's nice to be able to supply an alternate Comparator object to the PriorityQueue. My Comparator would simply order the objects with respect to their 'sequence' and ignores their 'values'.

The PriorityQueue class must be parameterized with a "A <% Ordered[A]"

From what I've read, this means my class must extend Ordered[A] or I must provide an "implicit def" type conversion to Ordered[A], which, honestly, feels inelegant.

The Java solution seems more "functional" allowing me to pass a Comparator function-like object instead of forcing me into a class hierarchy or monkeypatching my class.

I realize there are alternatives to using PrioirityQueue, but I feel like I may be bumping up against the Scala learning curve here and don't want to give up without exploring this design decision fully.

Is this just an unfortunate decision in the Scala library or am I misunderstanding some sort of calling convention that makes PriorityQueue more usable and 'functional'?

Thanks

我有一个事件优先级队列，但有时事件优先级会发生变化，所以我想将事件请求者的迭代器维护到堆中。如果优先级发生变化，我希望在 log(n) 时间内调整堆。我将始终只有一个迭代器指向堆中的每个元素。

我正在使用一个优先级队列，它最初将其元素的优先级基于启发式。随着元素出列，启发式方法会更新，并且当前队列中的元素可能会增加其键。

我知道有些堆（特别是斐波那契堆）已经摊销了 O(1) 减少键操作，但是是否有任何堆结构在增加键操作上有类似的界限？

对于我的应用程序，这远非性能问题（二进制堆工作正常），这实际上只是学术好奇心。

编辑：澄清一下，我正在寻找一种数据结构，其增加键操作的时间比 O(logn) 快，而不是减少键。我的应用程序从不减少密钥，因为启发式高估了优先级。

Priority receive in Erlang can easily be implemented as follows:

I am reading a paper called Priority Messaging made Easy, by Nyström, in which they describe the following problem:

The main problem with the [code] example [above], is that we do not take into consideration that when evaluation is resumed from the inner blocking receive we may have more than one message in the mailbox. In a worst case scenario, all but the first, of potentially a huge number, of elements could be priority messages. In this scenario we would actually have accomplished the very opposite of what we intended to do.

I don't completely get this.

Question (1): I assume that the inner blocking receive will be 'called' (i.e. resumed) as soon as one message has arrived in the message queue, right? Is it realistic to assume that in the short time it takes to resume from the inner blocking receive, there would already be a whole bunch of messages waiting in the queue?

Question (2): Also, the worst case scenario is described as a queue with one normal message and a lot of priority messages. Since all the receive clauses are first checked against the first message in the queue, and then against the second message in the queue, ...(source: this book, page 69-70) shouldn't this be: a lot of normal messages with at the end of the queue a priority message?