Position index for binary priority queues?

Question

So, let's say I have a priority queue of N priority elements, where N is in thousands, using the priority order implemented with the binary heap . I understand the EXTRACT-MIN and INSERT primitives (see Cormen, Leiserson, Rivest , which uses -MAX , not -MIN ).

But DELETE and DECREASE-KEY both seem to require that the priority queue be able to find the index of the element in the heap specified by the element itself (alternatively, this index should be set by the consumers of the priority queue, but this seems like an abstraction violation) .... which Looks like oversight. Is there a way to do this efficiently without adding a hash table on top of the heap?

Answer 1

That's right, I think the point here is that to implement the priority queue you can use the binary heap for which the API uses the index (i) for its HEAP-INCREASE-KEY (A, i, key), but the interface to the priority queue can be allowed to accept an arbitrary key. You can have a priority queue encapsulating key-> index map information. If you need PQ-INCREASE-KEY (A, old, new) to work in O (log n), you better have O (log n) or the best indexing key, which you will be aware of the latest developments. This could be a hash table or other quick search structure.

So, to answer your question: I consider it inevitable that the data structure needs to be supplemented in some way.

Answer 2

FWIW, and if someone is still looking for something similar, I recently looked at an implementation for an indexed priority queue, doing one of Coursera's algorithmic courses.

The main point is to enable reverse lookup, using 2 arrays to support the operations that the OP claimed.

Here's an explicit implementation for the Min Ordered Indexed Priority Queue .

Answer 3

“But DELETE and DECREASE-KEY both seem to require the priority queue to find the index of the element in the heap given by the element itself,” it’s clear from the code that at least some of these methods use the index in heap, and not an item priority. It’s clear that I am an index in HEAP-INCREASE-KEY:

 HEAP-INCREASE-KEY(A, i, key) if key < A[i] then error 'new key is smaller than current key" A[i] <-- key ... 

So, if it is an API, use it.

Answer 4

I modified my node class to add a heapIndex member. This is supported by the heap as nodes are replaced during insertion, deletion, reduction, etc.

This destroys encapsulation (my nodes are now tied to a heap), but it works fast, which was more important in my situation.

Answer 5

One way is to split the heap into elements on one side and organizations on the other.

For full functionality, you need two relationships: a) If the heap is located (for example, Root), find the Element located there. b) Given the element, find its location of the heap.

The second is very simple: add the value "location" (most likely, the index in the array based on the array), which is updated every time the item is moved to the heap.

The first is also simple: instead of storing elements, you simply save a bunch of pointers to Elements (or array indices). Now, given the location (e.g. Root), you can find the element located there by dereferencing it (or accessing the vector).

Answer 6

But DELETE and DECREASE-KEY both seem to require the priority queue to find the index of the item in the heap specified by the item itself

Actually, this is not so. You can implement these operations in non-indexed graphs, linked lists, and "traditional" search trees using the precursor and successor pointers.