A priority queue retrieves elements according to associated priority rather than arrival order. Binary heaps implement this access pattern efficiently by keeping the minimum or maximum element readily available. section 1.0 section 1.2
Choose the heap variant and operation according to the priority you need:
- Use a min-heap when retrieval should return the smallest priority value; use a max-heap when it should return the largest. section 1.2
- Keep the heap as a complete binary tree: levels fill from left to right, while each parent remains smaller or larger than its children. section 1.2
- Support isEmpty, insert, getMin or getMax, and extractMin or extractMax; insertion and extraction restore the heap through heapify operations. section 1.2
- Expect O(1) access to the extreme element, O(log n) insertion and extraction, and O(n) construction from an unsorted array. section 1.2 section 1.5
Array-backed heap
For a node at index i, calculate its left child at 2i + 1, its right child at 2i + 2, and its parent at (i - 1) / 2. In the max-heap example, the value 39 at index 1 has children at indices 3 and 4 and its parent at index 0. section 1.2
Inspect the heap and its underlying array representation together to connect the tree property with priority-queue storage. section 1.2






