1

I was going through Djikstra's algorithm when I noticed, I could update keys in heap(with n keys) in O(logn) time (last line in the pseudocode). How do I update keys in heaps in C++, is there any method in priority_queues to do this? Or do I have to write my own heap class to do achieve updates in O(logn) like this?

Edit 1:
Clarifying my need - for a binary heap with n elements -
1) Should insert new values and find & pop minimum values in O(logn)
2) Should update already present keys in O(logn)

I tried to come up with a way to implement this using make_heap, push_heap, pop_heap, and a custom function for update as John Ding suggested.

However I am facing a problem in making the function, I first need to find the location of the key in the heap. Doing this under O(logn) in a heap requires a lookup array for position of keys in heap, see here (I don't know of any other way). However these lookup tables won't be updated when I call push_heap or pop_heap.

NUMBART
  • 52
  • 9
  • Are you asking, in effect, "how do I change the priority of elements already in a `priority_queue`?" or more abstractly "if I need to change the priority of elements in a queue, what C++ container should I use?" – tadman Mar 05 '20 at 04:51
  • Right, How do I do that for a priority_queue with n elements, in O(logn) time? If it is not possible, how do you suggest I do it in a different way. I wish to update the key of an already present element in the priority_queue. – NUMBART Mar 05 '20 at 04:54
  • You will need to benchmark this to see how it works in *your* specific use-case, but some sorting algorithms work very quickly on nearly sorted lists, so if you're just changing a handful of entries you may be able to use a `list` and just sort it on any change. – tadman Mar 05 '20 at 04:57
  • 1
    You could also [remove the element](https://stackoverflow.com/questions/19467485/how-to-remove-element-not-at-top-from-priority-queue) and reinject it, or get fancy and make a `reemplace()` function that does this for you. – tadman Mar 05 '20 at 04:58
  • sorting in would take atleast O(n) time in a nearly sorted list too right? you would need to move it back in place. – NUMBART Mar 05 '20 at 04:59
  • Presumably at least, but if your queues are small that's not going to be that painful. It really depends on what kind of parameters you're operating within. If you're dealing with lists of >1e6 items you'll need to be very careful about how you manipulate things. I'd even suggest making a lightweight "proxy" entry that you can insert and later "null" out, reinserting a new proxy with the new priority. When you pull from the queue if you get a null proxy, keep fetching until you get a "real" entry. – tadman Mar 05 '20 at 05:01
  • That trades of memory for speed, but it could work if your changes are infrequent and potentially costly in terms of sorting. – tadman Mar 05 '20 at 05:02
  • Assign it to a new one – asmmo Mar 05 '20 at 05:03
  • I am unable to upvote your, remove element or create reemplace function comment. I have never done this before. So are we customizing the priority_queue, for our own use in those approaches? – NUMBART Mar 05 '20 at 05:06

3 Answers3

2

You can optimize dijktra algorithm with priority_queue. It is implemented by a binary heap, where you can pop the top or push in a element in O(logN) time. However, due to the encapsulation of priority_queue， you cannot modify the key(more pricisely, decrease the key) of any element.

So our method is to push multiple elements into the heap regardless of whether we have multiple elements refering to the same node.

for example, when

Node N : distance = 30, GraphNode = A(where A refers to one node in the graph, while N is one node in the heap)

is already in the heap, then using the priority_queue cannot help you do such a operation when we try to relax Node N:

decrease_key_to(N, 20)

by decreasing key can make the heap always include less than N elements, but it's cannot be implemented by priority_queue

What we can do with it is to add another node in the heap:

Node N2 : distance = 20, GraphNode = A
push N2 into the heap

That's corresponding to priority_queue::push

So you may need to implement a binary heap supporting decrease_key yourself or find an implementation online, and store a table of pointers pointing to every element in a heap to know access elements through nodes in the graph.

As an extension, using Fibonacci heap can even make decrease_key faster, that's the ultimate level of Dijkstra, Haha :)

Problem of last version of my answer:

We cannot locate the element pushed in to the heap using push_heap.

Community
  • 1
  • 1
con ko
  • 1,368
  • 5
  • 18
  • John, my present implementation of djikstra is the first one you have mentioned here. Can you add though how you are going to implement decrease_key(x, new_val) using make_heap, push_heap and pop_heap. Will we not get stuck because push_heap and pop_heap only work at the end of the array. – NUMBART Mar 07 '20 at 04:28
  • I didn't know about Fibonacci heaps, I will check it out. What complexity does Djikstra come down to with it? – NUMBART Mar 07 '20 at 04:29
  • I think you meant, we can implement the decrese_key method the others are already present, right. Thank you. – NUMBART Mar 07 '20 at 04:39
  • 1
    @NUMBART you can simply search for heap based-on arrays on Github or sth, and you only need to copy the `decrease_key` function and use standard library to build, push, pop the heap. If I didn't get it wrong, I estimate that the complexities of using `priority_queue`, binary heap with a `decrease_key`, Fibonacci heap are `O(ElgE)`, `O(ElgN)`, `O(NlgN) amortized`, respectively. – con ko Mar 08 '20 at 02:58
  • @NUMBART I didn't see your question. Sorry," Will we not get stuck because push_heap and pop_heap only work at the end of the array.". No. `decrese_key` doesn't require the heap to be node-based. – con ko Mar 08 '20 at 14:59
  • @NUMBART My fault. I didn't notice that `push_heap` returns `void`. I'll edit it. – con ko Mar 11 '20 at 06:20
0

In order to do this, you need more than the priority_queue provides: you need to know where in the underlying container the element to be updated is stored. In a binary heap, for example, you need to know the position of the element for which you want to change the priority. With this you can change the priority of the element and then restore the heap property in O(log n) by bubbling the modified element up or down.

For Dijkstra, if I remember correctly, something called Fibonacci heap is more efficient than a binary heap.

Daniel Junglas
  • 5,830
  • 1
  • 5
  • 22
  • I will definitely check out Fibonacci heaps, as both answers suggest it. Also, tadman had shared this link on [remove element](https://stackoverflow.com/questions/19467485/how-to-remove-element-not-at-top-from-priority-queue). I am not entirely sure about the implementation, but do you think it is possible to delete it in log(n) there and then reinsert it. – NUMBART Mar 07 '20 at 04:33
  • Sorry, I am not sure either. In general you can definitely implement removal in O(log(n)) time but I am not clear whether the suggested implementation does that. – Daniel Junglas Mar 09 '20 at 09:09
0

Unfortunately, std::priority_queue doesn't support updates of entries in the heap, but you may be able to invalidate entries in the heap and wait for them to percolate up to the root from where they can eventually be deleted. So instead of changing an existing entry, you invalidate it and insert another one with the new priority. Whether you can live with the consequences of having invalid entries filling up the heap, is for you to judge.

For an idea how this might work in practice, see here.

sh-
  • 941
  • 6
  • 13