position index for binary heap priority queues?

Question

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?

Answer 1

"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:

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

So if that's the API, use it.

Answer 2

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.

Answer 3

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.