60

I am working on an application that demonstrates the Djikstra's algorithm, and to use it, I need to restore the heap property when my elements' value is decreased.

The problem regarding the complexity is that when the algorithm changes the value of an element, that element's index in the internal structure (heap in this case) used for the priority queue is unknown. As such, I currently need to do an O(n) search, in order to recover the index, before I can perform an actual decrease-key on it.

Moreover, I am not exactly sure about the actual code needed for the operation. I am using the D-Heap here for my Priority Queue. Pseudocode would help, but I would prefer an example in Java on how this should be done.

jathanasiou
  • 882
  • 2
  • 8
  • 17
  • 1
    See http://en.m.wikipedia.org/wiki/Dijkstra's_algorithm#Running_time. – Oliver Charlesworth Jun 09 '13 at 11:27
  • 10
    From the link above: "To avoid O(|V|) look-up in decrease-key step on a vanilla binary heap, it is necessary to maintain a supplementary index mapping each vertex to the heap's index (and keep it up to date as priority queue G changes), making it take only O(log |V|) time instead." – Brainstorm Jun 09 '13 at 11:30
  • @Brainstorm I did consider using mapping but I was worried about the effect it might have on other operations. I am guessing this is the only way it can be done though. – jathanasiou Jun 09 '13 at 11:37

4 Answers4

45

You can do following: store a hashmap inside your heap that maps your heap values to heap indexes. Then you should extend your usual heap-logic just a bit:

on Swap(i, j): 
    map[value[i]] = j; 
    map[value[j]] = i;

on Insert(key, value): 
    map.Add(value, heapSize) in the beginning;

on ExtractMin: 
    map.Remove(extractedValue) in the end;

on UpdateKey(value, newKey): 
    index = map[value]; 
    keys[index] = newKey;

BubbleUp(index) in case of DecreaseKey, and BubbleDown/Heapify(index) in case of IncreaseKey, to restore min-heap-property.

Here's my C# implementation: http://pastebin.com/kkZn123m

Insert and ExtractMin call Swap log(N) times, when restoring heap property. And you're adding O(1) overhead to Swap, so both operations remain O(log(n)). UpdateKey is also log(N): first you lookup index in a hashmap for O(1), then you're restoring heap property for O(log(N)) as you do in Insert/ExtractMin.

Important note: using values for index lookup will require that they are UNIQUE. If you're not ok with this condition, you will have to add some uniqueue id to your key-value pairs and maintain mapping between this uniqueue id and heap index instead of value-index mapping. But for Dijkstra it's not needed, as your values will be graph nodes and you don't want duplicate nodes in your priority queue.

nbro
  • 15,395
  • 32
  • 113
  • 196
ptkvsk
  • 2,096
  • 1
  • 25
  • 47
  • 2
    You could also just use an array such that `array[vertex id] = heap index` or `-1` for absent. It might take more memory, but it's faster and simpler than hashmap (no resize, conflicts). And the memory does not matter much since you already have to keep the graph somewhere in an array, so that would just add another `int` for each vertex. – Ciro Santilli OurBigBook.com Apr 11 '15 at 08:53
  • 3
    @Ciro - What you have described is a direct access hashtable, but its use requires that each of your n elements "hash" to a unique value between 0 and n-1. If your vertices don't have a "vertex id" and you can't or don't want to dynamically add attributes to the vertices you can't use a vanilla array. If you could add such an attribute you'd be better off just adding a "heap index" attribute anyway. A hashtable is the generic solution here with O(1) amortized time on operations and there won't be any resizing. – Dave Aug 31 '15 at 23:59
  • @Dave Why wouldn't there be any resizing? – Marcus Johansson Sep 26 '16 at 18:23
  • @lonelyass to use a hash would add an O(log(n)) overhead to Swap, not O(1), that is not good. – VinGarcia Jun 22 '17 at 00:19
  • 1
    Also, about @CiroSantilli709大抓捕六四事件法轮功 idea. We could allow the user of the Hash to manage the array's memory. On each insertion, the Hash would require an optional ID (of a position the user knows to be empty) and on each extraction, we would also return the now emptied ID. Which is not simple but could provide optimal memory and time complexity. – VinGarcia Jun 22 '17 at 00:22
23

Per this SO question it is unnecessary to have a decrease-key method in order to implement Dijkstra's Algorithm.

You can simply add an item to the priority queue as many times as necessary and keep track of which nodes you have visited to weed out the duplicates. The first time you actually visit a node by popping it off of the queue, you have found the shortest path to that node and can ignore all future occurrences of it on the priority queue.

Having many extra nodes on the priority queue is not much of a problem because it is an O(log N) structure. (You have to do about 20 comparisons for 1 million items and 30 comparison for 1 billion items.)

Edit: Following up on this question later, I'm a bit disappointed by my answer: all of those things will have to come off of the queue unless you do some special canipulations later. Like many things in life, it comes down to how you manage your memory and the costs associated with doing so. But the general point remains: decrease-key is not necessary, even if it might be desirable.

Community
  • 1
  • 1
Richard
  • 56,349
  • 34
  • 180
  • 251
  • 1
    Following up on this question later, I'm a bit disappointed by my answer: all of those things will have to come off of the queue unless you do some special canipulations later. – Richard Feb 25 '16 at 17:03
  • 3
    I'm a bit surprised that you're a bit disappointed. In actual practice, there won't be so many of "all of those things" that performance would noticeably degrade. There's a nice article at http://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-priority_queue-stl/ that takes just this approach when using C++ STL. – Erick G. Hagstrom Mar 21 '16 at 12:23
  • 4
    @Richard this is a practical solution. We use this in many places in our application and we maintain a separate unordered_set that tracks visited nodes. Your solution is way better when we look at complexities and overhead of decreasing keys for every key inserted. – Chenna V Sep 10 '16 at 23:03
  • 5
    This way still gets an asymptotic time complexity of O(mlogn). Why? Well in the worst case, we pop from the heap m times, and push to the heap m times. Because the heap grows to maximum size m, each operation is O(logm). So in total, we have a time of O(mlogm + mlogm) = O(mlogm). But m = O(n^2) (hand-shaking lemma), so we have O(mlog(n^2)) = O(mlogn) time. For large graphs, decrease-key makes little difference. Practically, its highly debatable whether the added difficulty in implementing decrease-key is worth any non-asymptotic time benefits. The space however, does reduce from O(m) to O(n). – James Lawson Oct 29 '16 at 09:48
  • @JamesLawson from another answer: not using DECREASE-KEY may be faster in practice https://stackoverflow.com/a/18540646/3163618 – qwr Oct 07 '21 at 20:04
0

If you are using c++ stl make_heap()/pop_heap()/push_heap(), there is no way to keep an index from node id to index in the underline heap vector, I think you should implement your own heap functions to achieve O(logn) in Increase-Key/Decrease-key operation.

zach
  • 184
  • 2
  • 8
  • Ok, but it _is_ possible to use STL just by reinserting rather than decreasing a key that changes. http://www.geeksforgeeks.org/dijkstras-shortest-path-algorithm-using-priority_queue-stl/ – Erick G. Hagstrom Mar 21 '16 at 12:25
0

I had implemented the same thing. In the MinHeap class, I had added a dictionary that is used to access the item in O(1). And on decrease key, it will be bubbled up in O(logn) time.

class MinHeap:
def __init__(self, array):
    self.heap = self.buildHeap(array)
    self.idx_of_element = {}

def getParentIdx(self, idx):
    return (idx - 1) // 2

def getLeftChildIdx(self, idx):
    return idx * 2 + 1

def getRightChildIdx(self, idx):
    return idx * 2 + 2

def buildHeap(self, array):
    # Write your code here.
    lastIdx = len(array) - 1
    startFrom = self.getParentIdx(lastIdx)
    for i in range(startFrom, -1, -1):
        self.siftDown(i, array)
    return array

# this is min-heapify method
def siftDown(self, idx, array):
    while True:
        l = self.getLeftChildIdx(idx)
        r = self.getRightChildIdx(idx)

        smallest = idx
        if l < len(array) and array[l] < array[idx]:
            smallest = l
        if r < len(array) and array[r] < array[smallest]:
            smallest = r

        if smallest != idx:
            array[idx], array[smallest] = array[smallest], array[idx]
            self.idx_of_element[self.heap[idx]], self.idx_of_element[self.heap[smallest]] = self.idx_of_element[self.heap[smallest]], self.idx_of_element[self.heap[idx]]
            idx = smallest
        else:
            break
Raj
  • 173
  • 2
  • 8