键值变化的优先级队列
我必须模拟优先级队列。队列中的密钥会定期更改。队列必须能够：添加元素和删除元素。最好的方法是什么（具有最佳的复杂性）？最好的数据结构是什么？
I must to simulate a priority queue. Keys in queue are periodically changed. Queue must be able: add element and delete element. What is the best way to do it (with the best complexity)? What is the best data structure?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
我推荐以下两种方法之一：
I would recommend one of two approaches:
如果您正在寻找一种可以支持任意键不断变化以及任意键的删除/添加的数据结构[任意==不是这个答案中的头部]，则常规堆不会解决这个问题，因为它不不能保证快速搜索任意元素，只能搜索到头部。
您可以选择完全有序的结构，例如 平衡 BST，并缓存最小/max 每当树被修改时。 [最小值是最左边的元素，最大值是最右边的元素]。
这将使您：
删除、修改、添加：
O(logn)查找最小值/查找最大值：
O(1)If you are looking for a data-structure that can support constant changes in arbitrary keys, and removals/additions of arbitrary keys [arbitrary == not the head in this answer], a regular heap won't do the trick, since it doesn't guarantee quick search for arbitrary elements, only to the head.
You could go for a fully ordered structure, such as a balanced BST, and cache the min/max whenever the tree is modified. [the min is the leftest element, the max is the rightest element].
This will allow you:
delete,modify,add:
O(logn)findMin/findMax:
O(1)总是很难说什么是“最好的”数据结构。一般来说，二叉堆是一个非常好的优先级队列，尽管更改项目的优先级很困难。我过去所做的是创建一个结合字典和堆的数据结构。该字典以项目的标识符为键，并跟踪每个项目在堆中的位置。当在堆中添加、删除或移动项目时，其在字典中的位置会更新。事实证明这很便宜。
现在，当您想要更改某个项目的优先级或从优先级队列中删除任意项目时，您可以在字典中查找它 (
O(1)) 以获取其在堆中的位置。从那里开始，移动或删除它是一个O(log n)操作。您还可以使用平衡二叉树作为优先级队列。保留一个“最低节点”指针很容易，并且树上的操作是
O(log n)。如果插入和删除相当分散，那么这应该表现得相当好。缺点是实现自平衡二叉树的代码有点复杂。另一种可能性是为优先级队列使用跳过列表。我的测试表明，跳跃列表优先级队列与基于二进制堆的优先级队列相比毫不逊色，但有一个很大的优势：查找一项的时间复杂度为
O(log n)而不是O(n ）。跳跃列表的实现并不比二进制堆困难多少。我倾向于使用跳过列表，因为它比组合堆/字典更容易管理，并且它比平衡二叉树性能更好。
It's always difficult to say what the "best" data structure is. In general, a binary heap makes a very good priority queue, although it is difficult to change an item's priority. What I did in the past is create a data structure that combines a dictionary and a heap. The dictionary is keyed by the item's identifier, and keeps track of each item's location in the heap. When an item is added, removed, or moved in the heap, its location is updated in the dictionary. This turns out to be inexpensive.
Now when you want to change an item's priority or remove an arbitrary item from the priority queue, you can look it up in the dictionary (
O(1)) to get its position in the heap. From there, it's anO(log n)operation to move or remove it.You could also use a balanced binary tree for your priority queue. It's easy enough to keep a "lowest node" pointer, and operations on the tree are
O(log n). If insertions and removals are fairly well scattered out, this should perform reasonably well. The drawback is that the code to implement a self-balancing binary tree is a bit involved.Another possibility is to use a skip list for your priority queue. My tests show that a skip list priority queue compares favorably with a binary heap based priority queue, but has one big advantage: looking up an item is
O(log n)rather thanO(n). And a skip list isn't much more difficult to implement than a binary heap.I would tend toward using the skip list because it's easier to manage than the combined heap/dictionary, and it will perform better than the balanced binary tree.
如果您只是将数字存储为键，则 ArrayList 类应该可以正常工作。
If you're just storing numbers as keys, the ArrayList class should work fine.