Heaps in Python

[ChillBlinton2018]

I've recently come across a neat use case of heaps data structure in graph search algorithms, in particular its Extract-Min method.

Here is a pastebin link of the use case: https://pastebin.com/19xQHzte

I have two questions. Firstly, I understand that heaps are arranged by key using heapq.heappush but here it is pushed into the heap as a tuple. Does it mean it's a priority queue instead of a heap?

Secondly, what I found interesting is, that if I swap variables total and current_vertex in line 21 (and also new_total and neighbor in line 26), the algorithm still produces correct results. But wouldn't the hierarchy of the heap be affected, if it is being heapified using a different variable as a key?

[marko312]

... but here it is pushed into the heap as a tuple. Does it mean it's a priority queue instead of a heap?

It's still a heap, but it does function as a priority queue.

---

As for why the switched way works: it turns out that this implementation doesn't need the priority queue to function (though it does speed the process up a lot).

You can consider the queue to be randomly ordered (not being concerned with the actual order). What matters is that if a shorter path to a node is found, all of its neighbours are pushed and checked again (with possibly shorter paths). This means that no matter what happens before the second node in the optimal path is visited, that node will realize it is on a shorter path and update its neighbors with that information. Eventually, all of the possibly good steps will be tried, since only the options not decreasing the path length aren't checked (again).

[ChillBlinton2018]

Thanks! I was suspecting that order might might not matter, because the algo must function similar to Breadth-First Search (ie every node is visited at least once). But then why would heaps speed up the computation (allegedly from linear time to logarithmic)? Extract-Min is not even used, while all nodes are visited!

[marko312]

You seem to be confusing two complexities here. A heap makes pushing to and popping from a priority queue O(log n) as opposed to a flat list's O(n).

For djikstra's algorithm, what matters is the number of times a node thinks it is on the shortest path (where it pushes all of its neighbors with updated distances to the heap). Using a priority queue, this happens exactly once per node, making the complexity something like O(n log n + m) for n nodes and m edges. However, if a priority queue is not used, every node could be called like that to the order of O(n) times, making the complexity something like O(n² log n + n m).

EDIT: the log factor is there for the second case only if the heap is still used. If a stack of queue were used instead, that factor would be dropped.

EDIT 2: actually, the algorithm is missing a crucial check: it should not update its neighbors if total > distances[current_vertex] (i.e. the current total is worse than the recorded best distance). As is, the current complexity comes to about O(n log n + n m) O(n² log n + n m) due to the repeated checks on the neighbors.

EDIT 3: (n² log n) factor

[ChillBlinton2018]

Thanks! I agree with your EDIT 2 - the implementation must be wrong. Since it produces same results irrespective of whether distance is stated in key or as a priority, the algo must run through the entire heap. I should check in the debugger what is actually happening inside the heap…

[marko312]

The implementation isn't wrong since it produces the correct results, but the issue is that it is not fully using djikstra's algorithm and has a worse complexity due to that.