Problem

Design a min-heap data structure from scratch (without using a library priority queue) that supports the following operations:

• insert(x) — add an integer.
• getMin() — return the smallest element without removing it.
• extractMin() — remove and return the smallest element.
• deleteAt(i) / decreaseKey(i, newVal) — optional extensions.
• isEmpty(), size().

All operations except getMin must run in O(log n).

Input / Output

A sequence of operations; return the results of getMin and extractMin calls in order. Return -1 (or raise) when the heap is empty.

Examples

Operations: insert(5), insert(3), insert(8), getMin(), extractMin(), getMin() Output: 3, 3, 5

Constraints

• Up to 10^5 operations.
• Values fit in 32-bit signed integers.

Approach

Store the heap in a dynamic array. For index i: parent is (i-1)/2, children are 2i+1 and 2i+2. The invariant is arr[parent] <= arr[child] for every edge.

insert(x) — append x at the end, then sift up: while x is smaller than its parent, swap them. Height is log n, so at most log n swaps.

getMin() — return arr[0].

extractMin() — save arr[0], move the last element to index 0, shrink the array, then sift down from index 0: repeatedly swap with the smaller child while a child is smaller.

decreaseKey(i, v) — set arr[i] = v and sift up.

deleteAt(i) — decreaseKey(i, -inf) then extractMin().

Handle the empty heap explicitly in getMin and extractMin.

Complexity

• insert, extractMin, , : O(log n)