CODEWITHSUNDEEP
data-structurespriority-queue
Jason S
Jason S

Reputation: 189836

position index for binary heap priority queues?

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?

Upvotes: 4

Views: 4006

Answers (6)

anirvan
anirvan

Reputation: 4877

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.

Upvotes: 1

A T
A T

Reputation: 13846

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

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.

Upvotes: 0

Gaminic
Gaminic

Reputation: 581

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).

Upvotes: 0

Saxon Druce
Saxon Druce

Reputation: 17624

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.

Upvotes: 0

bockmabe
bockmabe

Reputation: 350

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.

Upvotes: 1

hughdbrown
hughdbrown

Reputation: 49033

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

Upvotes: 0

Related Questions