<aside> 🏔️

L7 — Use Heaps! covers the heap data structure (definition, two properties), adding elements (percolate up), priority queues, removing the minimum (percolate down), array implementation with index formulas and bit-shift optimisations, Java code for a heap-based priority queue, time complexity analysis, and heap sort.

</aside>

📋 At a Glance

• [ ] State the two properties that define a (min-)heap
• [ ] Know the difference between min-heaps and max-heaps
• [ ] Trace adding an element with percolate up
• [ ] Understand the priority queue interface and its connection to heaps
• [ ] Trace removeMin with percolate down (replace root with last, then sink)
• [ ] Know why promoting a child directly breaks completeness
• [ ] Memorise the array navigation formulas (parent, left child, right child)
• [ ] Understand the bit-shift optimisations for navigating the array
• [ ] Read through the Java HeapPQ implementation
• [ ] Know that add and removeMin are Θ(log n) worst case
• [ ] Trace a full heap sort example by hand
• [ ] Know heap sort is O(n log n) but not in-place (standard heap sort is in-place but not examinable)

1. Heaps — Definition

A (min-)heap is a binary tree satisfying two constraints:

1. Complete tree — every level above the lowest is fully occupied, and the lowest level is filled left to right
2. Heap order — each child has a value greater than or equal to its parent