_Muhammad's blog

Need help to calculate the complexity of solution for D. Abandoning Roads using a normal queue.
By _Muhammad, history, 6 years ago, In English

For 1149D - Abandoning Roads I implemented this code using a priority queue. This is tutorials logic. And took 639ms.

But when I implemented same logic using a single normal queue it took 280ms. ( My code ).

Can any one tell me why without priority queue Dijkstra working much faster. Please help me to understand the complexity for 2nd code ( without priority queue ) . I understood the complexity of the 1st code ( with priority queue ).

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Priority Queue is a implemented as a Max Heap, therefore the push() operation takes O(logn). On the other hand, queue can be implemented using linked-lists resulting in a O(1) push() operation. Remember that priority-queue sorts the elements while queue doesn't. That's why the queue implementation is faster as you get rid of the O(log(n)) factor.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    But I implemented Dijkstra using queue. Many node may update multiple time. Normally Dijkstra using normal queue has O(n^2) complexity.

    → Reply