A max heap is a complete binary tree where every parent is larger than its children. It provides quick access to the maximum element and commonly implements priority queues. section 1.2
A max heap supports these operations:
- isEmpty checks whether the heap contains elements. section 1.2
- insert adds an element and restores ordering with heapify up; it costs O(log n). section 1.2
- getMax returns the maximum without removing it in O(1). section 1.2
- extractMax removes and returns the maximum, then uses heapify down in O(log n). section 1.2
- Building a heap from an unsorted array costs O(n), rather than repeatedly inserting elements. section 1.2
Array representation
Heaps are usually stored in arrays. For a node at index i, the left child is 2i + 1, the right child is 2i + 2, and the parent is (i - 1) / 2. Thus, a value such as 39 at index 1 has children at indices 3 and 4 and a parent at index 0. section 1.2

