A binary heap is a complete binary tree organized for quick access to one extreme element. A min-heap keeps each parent smaller than its children; a max-heap keeps each parent larger. Choose a min-heap when the minimum matters, or a max-heap when the maximum matters—not both at once. section 1.2
Heaps commonly use an array rather than linked tree nodes. For an element at index i, the left child is at 2i + 1, the right child at 2i + 2, and the parent at (i − 1) / 2. This layout preserves the complete-tree shape without storing explicit links. section 1.2
A heap supports a compact set of priority-oriented operations:
- isEmpty checks whether the heap contains no elements. section 1.2
- insert adds an element and restores the heap property with heapify up; its cost is O(log n). section 1.2
- getMin or getMax returns the extreme element without removing it in O(1). section 1.2
- extractMin or extractMax removes and returns the extreme element, then restores order with heapify down in O(log n). section 1.2
- Building a heap directly from an unsorted array takes O(n), which is more efficient than inserting all elements individually. section 1.2
Reading a heap stored in an array
In a max-heap, suppose 39 is stored at index 1. Its left child is at index 2 × 1 + 1 = 3, its right child at index 4, and its parent at index (1 − 1) / 2 = 0. The array indexes expose the tree relationships directly. section 1.2
Use the heap figure to connect the complete-tree shape with its array representation. section 1.2



