A min-heap is a complete binary tree where every parent is smaller than its children. It provides quick access to the minimum element and commonly implements priority queues. section 1.2
Core operations balance fast minimum access with logarithmic updates:
- isEmpty checks whether the heap contains elements. section 1.2
- insert adds an element and restores order with heapify up in O(log n). section 1.2
- getMin returns the minimum without removing it in O(1). section 1.2
- extractMin removes and returns the minimum, then uses heapify down in O(log n). section 1.2
Array representation
When a heap is stored in an array, an element at index i has children at 2i + 1 and 2i + 2, and its parent at (i - 1) / 2. Building a heap from an unsorted array takes O(n). section 1.2


