Sign in to follow this  
Annoyed

[C++ Pointer hell]Heap decrease-key issue

Recommended Posts

Hi folks, I have implemented a heap using C++, std::vector<T> as container and it works. The heap is used as a priority queue (suprise!) and that works too... as long as key do not change while in queue. And here is why: I have X task initiators that have Y tasks each. The implementation is that X0,X1,...,Xn each have their own std::vector<TaskObj*> which hold the reference to their respective tasks. Now all task handers add their tasks (TaskObj*) into the heap in one bulk. Somehting like:
foreach TaskHandler
    foreach TaskObj*
        Heap.Add(task)
Heap.BuildHeap()

Now the heap is correct. But now initiator X1 would to like to decrease-key on it's own Y5 task say. Problem is that I have no idea of Y5's index in the heap container. Lets assume that the task is in the queue, is it possible to determine what index Y5 has in the container? If so how?

Share this post


Link to post
Share on other sites
Quote:
Original post by Annoyed

Now the heap is correct. But now initiator X1 would to like to decrease-key on it's own Y5 task say. Problem is that I have no idea of Y5's index in the heap container. Lets assume that the task is in the queue, is it possible to determine what index Y5 has in the container? If so how?


You need a separate index which you update as you build the heap.

Canonical way is to search the heap for the key.
Another is to use a map of sorts with task as key.
Third is to have Task to store the index.
Later two solutions require index be updated as the heap is built.

Implementations vary wildly as do the run-time characteristics. O(n) complexity is the same for all equivalent solutions.

Share this post


Link to post
Share on other sites
Thank you, I was hoping there was some magic pointer arithmetic trick to it.
Keys are not unique identifiers but the priority indicator (perhaps bad name convention =P), but I could add a ID I suppose.
But seems to me that storing the index with a node sounds good, then you can maintain it for every swap you perform during heap maintenance but then you need to decrement all indices when you pop one item from queue.
I was hoping to skip adding to the time complexity. But so be it.

Share this post


Link to post
Share on other sites
In fact this was better then I thought. Extracting from a heap mean you swap the first element and last element (maintain index on swap) and then remove the tail. Now all indices are consistent. And then you heapify on element 0 etc ...
This is good enough for me :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this