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
- Dijkstra's algorithm — An algorithm that finds the cheapest paths from one vertex to all others in a graph whose edge weights are never negative, using a min-heap.
- heapq — Python's standard-library module of functions that treat an ordinary list as a binary min-heap.
- min-heap — A heap in which every parent is less than or equal to its children, so the minimum is at the root; a max-heap reverses the order.
Taught in
- Heaps And Priority Queues — Algorithms & Data Structures for Working Engineers
- Dijkstra: Shortest Paths With A Priority Queue — Algorithms & Data Structures for Working Engineers