Indian Computing Olympiad

Training Material


Dijkstra's algorithm requires us, in each round, to

  1. Pick a vertex with minimum burning time
  2. Change the expected burning time for each neighbour

If we use an adjacency list representation, step 2 will be efficient (note that in this adjacency list we need to store the edge weight as well).

How do we do step 1 efficiently? Suppose we keep the list sorted.

  • If the list is an array
    • Search is fast (log n)
    • Insert is slow (n)
  • If the list is a linked list
    • Search is slow (n)
    • Insert is fast (constant time), once we know where to insert!

Instead, we can use a different data structure, called a heap.

Video material

Video lecture on Heaps, NPTEL online course on Design and Analysis of Algorithms (Lecture slides)

Some problems involving heaps