二进制堆优先级队列的位置索引？
假设我有一个包含 N 个具有优先级的项目的优先级队列，其中 N 为数千，使用通过 二进制堆。 我了解 EXTRACT-MIN 和 INSERT 原语（请参阅 Cormen、Leiserson、Rivest 使用 -MAX 而不是 -MIN）。
但是 DELETE 和 DECREASE-KEY 似乎都要求优先级队列能够在给定项目本身的堆中找到该项目的索引（或者，该索引需要由优先级队列的消费者给出，但这似乎是一种抽象违规）……这看起来像是一个疏忽。 有没有一种方法可以有效地完成此操作，而无需在堆顶部添加哈希表？
So let's say I have a priority queue of N items with priorities, where N is in the thousands, using a priority queue implemented with a binary heap. I understand the EXTRACT-MIN and INSERT primitives (see Cormen, Leiserson, Rivest which uses -MAX rather than -MIN).
But DELETE and DECREASE-KEY both seem to require the priority queue to be able to find an item's index in the heap given the item itself (alternatively, that index needs to be given by consumers of the priority queue, but this seems like an abstraction violation).... which looks like an oversight. Is there a way to do this efficiently without having to add a hashtable on top of the heap?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（6）
是的，我认为这里的要点是，为了实现优先级队列，您可以使用二进制堆，其 API 为其 HEAP-INCREASE-KEY(A, i, key) 采用索引 (i)，但是与优先级队列可以被允许采用任意键。 您可以自由地让优先级队列封装键->索引映射的详细信息。 如果您需要 PQ-INCREASE-KEY(A, old, new) 在 O(log n) 中工作，那么您最好有一个 O(log n) 或更好的索引查找键，并保持最新。 这可能是哈希表或其他快速查找结构。
所以，回答你的问题：我认为数据结构以某种方式增强是不可避免的。
Right, I think the point here is that for the implementation of the priority queue you may use a binary heap who's API takes an index (i) for its HEAP-INCREASE-KEY(A, i, key), but the interface to the priority queue may be allowed to take an arbitrary key. You're free to have the priority queue encapsulate the details of key->index maps. If you need your PQ-INCREASE-KEY(A, old, new) to to work in O(log n) then you'd better have a O(log n) or better key to index lookup that you keep up to date. That could be a hash table or other fast lookup structure.
So, to answer your question: I think it's inevitable that the data structure be augmented some how.
FWIW，如果有人仍然来寻找类似的东西 - 我最近在做 Coursera 的一门算法课程时偶然发现了一个索引优先级队列的实现。
基本要点是使用 2 个数组合并反向查找来支持 OP 所述的操作。
这是最小有序索引优先级队列的清晰实现。
FWIW, and if someone still comes looking for something similar — I recently chanced upon an implementation for an Indexed priority queue while doing one of the Coursera courses on Algorithms.
The basic gist is to incorporate a reverse lookup using 2 arrays to support the operations that the OP stated.
Here's a clear implementation for Min Ordered Indexed Priority Queue.
“但是 DELETE 和 DECREASE-KEY 似乎都需要优先级队列能够在给定项目本身的堆中找到该项目的索引”——从代码中可以清楚地看出，这些方法中至少有一些方法使用了索引堆而不是项目的优先级。 显然，i 是 HEAP-INCREASE-KEY 中的索引：
因此，如果这是 API，请使用它。
"But DELETE and DECREASE-KEY both seem to require the priority queue to be able to find an item's index in the heap given the item itself" -- it's clear from the code that at least a few of these methods use an index into the heap rather than the item's priority. Clearly, i is an index in HEAP-INCREASE-KEY:
So if that's the API, use it.
我修改了节点类以添加 heapIndex 成员。 这是由堆维护的，因为在插入、删除、减少等过程中交换节点。
这会破坏封装（我的节点现在绑定到堆），但它运行速度很快，这在我的情况下更重要。
I modified my node class to add a heapIndex member. This is maintained by the heap as nodes are swapped during insert, delete, decrease, etc.
This breaks encapsulation (my nodes are now tied to the heap), but it runs fast, which was more important in my situation.
一种方法是将堆分为一侧的元素和另一侧的组织。
为了获得完整的功能，您需要两个关系：
a) 给定一个堆位置（例如根），找到位于该位置的元素。
b) 给定一个元素，找到它的堆位置。
第二个非常简单：添加一个值“位置”（很可能是基于数组的堆中的索引），每次在堆中移动元素时都会更新该值。
第一个也很简单：您只需保留一堆指向 Elements（或数组索引）的指针，而不是存储 Elements。 现在，给定一个位置（例如根），您可以通过取消引用它（或访问向量）来找到位于该位置的元素。
One way is to split up the heap into the elements on one side and the organization on the other.
For full functionality, you need two relations:
a) Given a Heap Location (e.g. Root), find the Element seated there.
b) Given an Element, find its Heap Location.
The second is very easy: add a value "location" (most likely an index in an array-based heap) that is updated every time the element is moved in the heap.
The first is also simple: instead of storing Elements, you simply keep a heap of pointers to Elements (or array indeces). Now, given a Location (e.g. Root), you can find the Element seated there by dereferencing it (or accessing the vector).
实际上，事实并非如此。 您可以通过使用前驱指针和后继指针在无索引图、链表和“传统”搜索树中实现这些操作。
Actually, that's not true. You can implement these operations in an unindexed graph, linked-lists and 'traditional' search trees by having predecessor(s) and successor(s) pointers.