What is a Heap?

A heap is a tree-shaped data structure that obeys one simple invariant: every parent is smaller than (or equal to) its children. The smallest value always sits at the root, ready to be read in O(1). This particular flavor is called a min-heap; the mirror image with a largest-at-root invariant is a max-heap.

The clever bit is the storage. Even though we think of it as a tree, a heap lives in a flat array. For the node at index i:

• Its parent is at index (i - 1) / 2.
• Its left child is at index 2 * i + 1.
• Its right child is at index 2 * i + 2.

No pointers, no node objects: just index math. That makes heaps very cache-friendly and easy to implement.

The five main operations on a min-heap are:

1. Peek: Return the smallest value (the root).
2. Insert: Add a value and bubble it up to its place.
3. ExtractMin: Remove and return the smallest value.
4. Size: Return how many values are stored.
5. IsEmpty: Check whether the heap is empty.

Let's create a MinHeap class!