foreach TaskHandler
foreach TaskObj*
Heap.Add(task)
Heap.BuildHeap()
[C++ Pointer hell]Heap decrease-key issue
Author
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:
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?
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.
Author
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.
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.
Author
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 :)
This is good enough for me :)
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
