Indian Computing Olympiad

Heaps

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.

• Manipulating heaps
• Building a heap
• Max-heaps and min-heaps
• Heapsort
• Dijkstra's algorithm with heaps

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

Some problems involving heaps

• Backup (APIO 2007)
• Race (CEOI 2003)
• Sokoban