lazy deletion

Leaving outdated entries in a heap instead of removing them, and simply skipping them when they are popped.

In more detail

When Dijkstra's algorithm finds a cheaper route to a vertex, it pushes a new entry rather than updating the old one, which heapq cannot do efficiently. When the old, dearer entry is popped later, its distance is worse than the recorded one and it is ignored. The heap can hold up to E entries, hence O(E log E).

Related terms

Taught in

References