A binary heap is a tree-shaped implementation commonly used inside a priority queue. It keeps frontier elements ordered so popping returns the highest-priority item; in A*, that means the state with the lowest f(n) = g(n) + h(n). section 2.2
In the A* search setting, the heap-backed priority queue provides:
- Priority-based removal of the next frontier state rather than stack-like or queue-like traversal. section 2.2
- O(lg n) insertion and removal operations. section 2.2
- Comparison through Swift's Comparable protocol, using each node's cost plus heuristic. section 2.2
A* maze search
A* places maze nodes in an ascending priority queue and uses Manhattan distance as the heuristic, causing the next pop to favor the lowest estimated total path cost. section 2.2
