Queue vs Heap Queue (heapq)¶
Understanding why BFS uses queues and Dijkstra uses priority queues.
What is a Queue?¶
A queue works like:
First In
First Out
This is called:
FIFO¶
Example¶
[A, B, C]
Removing:
A
because:
A entered first
deque¶
Python provides:
from collections import deque
deque means:
double-ended queue
Useful operations:
append()
popleft()
Why BFS uses deque¶
BFS explores:
level by level
Example:
start
âââ A
âââ B
âââ C
BFS processes:
A first
then B
then C
because:
they were inserted first
BFS Behavior¶
ORDER OF ARRIVAL
This is PERFECT for:
deque
What is heapq?¶
heapq is Python's built-in:
Priority Queue¶
Difference from normal queue¶
A normal queue removes:
oldest element
A priority queue removes:
lowest cost first
Example¶
You insert:
(5, "B")
(1, "A")
(3, "C")
heapq automatically organizes:¶
lowest cost first
Then:
heapq.heappop(queue)
returns:
(1, "A")
EVEN IF:
A was inserted later
Why Dijkstra uses heapq¶
Dijkstra constantly asks:
"What is the CHEAPEST current route?"
NOT:
"What was inserted first?"
That is why:
deque
is not ideal for Dijkstra.
Dijkstra needs:¶
LOWEST COST FIRST
Which is exactly what:
heapq
does.
Dijkstra Example¶
import heapq
queue = []
heapq.heappush(queue, (2, "roof1"))
heapq.heappush(queue, (1, "corridorA"))
heapq.heappush(queue, (5, "goal"))
print(heapq.heappop(queue))
Output:
(1, "corridorA")
Visual Comparison¶
deque / BFS¶
ORDER OF ARRIVAL
A â B â C
heapq / Dijkstra¶
LOWEST COST FIRST
1 â 2 â 5
Fly-in Connection¶
BFS¶
Good for: - unweighted graphs - same movement costs
Dijkstra¶
Good for: - weighted graphs - movement costs - route optimization
Fly-in is:
Weighted Graph Pathfinding
So:
heapq + Dijkstra¶
fits the project much better.
Mental Model¶
BFS / deque¶
Think:
"Who arrived first?"
Dijkstra / heapq¶
Think:
"Who is currently the cheapest?"
Final Mental Image¶
deque¶
Supermarket line
First customer: - enters first - leaves first
heapq¶
Hospital emergency room
Most urgent patient: - treated first - even if arrived later