Implement Min Heap

Implement a min-heap — a priority queue that always keeps the smallest element reachable in O(1) — supporting:

insert(x) — add x to the heap.
getMin() — return the current minimum (called only when non-empty).
extractMin() — remove and return the current minimum (called only when non-empty).
size() — return the number of elements.

insert and extractMin should run in O(log n). Store the heap in an array using the standard index arithmetic: the children of i are 2i+1 and 2i+2, the parent is (i-1)/2.

Hints

· Stuck? Reveal one nudge at a time.

Store the heap in an array; the minimum lives at index 0.

insert: append at the end and swap upward while smaller than the parent.

extractMin: move the last element to the root, then sift it down past its smaller child.

Common doubts

Full sorting is O(n log n) per change; a heap keeps only enough order to expose the min, so insert and extract are O(log n).

It keeps the tree complete (no gaps), and a single sift-down then restores the heap property.

Swapping the smaller child up guarantees it ends ≤ its new sibling, preserving the min-heap property.

Interview follow-ups

· What an interviewer asks next.

Locate the element (needs an index map), lower its value, and sift it up.

Bottom-up heapify in O(n) instead of O(n log n).

Fun facts

A binary heap is how most standard-library priority queues (C++ priority_queue, Python heapq) are implemented.
getMin at O(1) with O(log n) updates is exactly the trade-off Dijkstra and Prim rely on.

Asked at

AmazonMicrosoftAdobe

Frequently Sometimes Occasionally

Example 1

Input: insert(5), insert(3), insert(8), getMin(), extractMin(), getMin()
Output: null null null 3 3 5
The minimum is 3; after extracting it, the new minimum is 5.

Example 2

Input: insert(2), size(), getMin()
Output: null 1 2
One element: size is 1 and the min is 2.

Constraints

- -10^9 <= x <= 10^9 - At most 2 * 10^4 operations - getMin / extractMin only on a non-empty heap

A min-heap keeps the smallest element at the root (index 0) of a complete binary tree stored in an array. The brute-force version — an unsorted list — makes insert trivial but pays O(n) to find the minimum on every getMin/extractMin. The real heap keeps the array partially ordered so the minimum is always at index 0, and repairs the order in O(log n) using two moves:

insert(x) — append x at the end, then sift up: while it's smaller than its parent, swap them. It rises to its correct level.
extractMin() — the answer is arr[0]. Move the last element to the root, drop the last slot, then sift down: while the node is larger than its smaller child, swap them. It sinks to its correct level.

getMin is just arr[0], and size is the array length. Each repair walks one root-to-leaf path, so it's O(log n).

Prerequisites

Before you start

· Concepts used directly in the solution.

Array-as-tree. parent (i-1)/2, children 2i+1 and 2i+2.

Sift up / sift down. the two O(log n) repairs behind insert and extract.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Are getMin/extractMin ever called on an empty heap?”

No — assume non-empty for those.

“Which child do I compare against in extractMin?”

The smaller child, so the swapped-up value stays ≤ its sibling.

The ideal opening — say it like this

I store the heap in an array with the min at index 0. Insert appends and sifts up; extract-min moves the last element to the root and sifts down.

Both repairs walk one root-to-leaf path, so insert and extract are O(log n) and getMin is O(1).

Understand the problem

Worked example — insert 5, insert 3, insert 8, getMin, extractMin, getMin

insert 5 -> [5]
insert 3 -> [5,3] sift up -> [3,5]
insert 8 -> [3,5,8]
getMin   -> 3
extractMin -> 3; move 8 up -> [8,5] sift down -> [5,8]; returns 3
getMin   -> 5

Key observations

1Aha

The min is always at index 0

The heap property forces the global minimum to the root.

2Aha

Insert sifts up, extract sifts down

Each disturbs a single path and is repaired in O(log n).

3Aha

extractMin swaps in the last element

Moving the last leaf to the root keeps the tree complete before sifting down.

Brute force vs optimal

	Unsorted list	Array binary heap
insert	O(1)	O(log n)
getMin	O(n)	O(1)
extractMin	O(n)	O(log n)

The heap wins whenever getMin/extractMin are frequent — which is the whole point of a priority queue. Full code is in the Approaches selector below.

Summary

Key takeaway

Keep the heap in an array with the min at index 0. insert appends + sifts up; extractMin swaps the last element to the root + sifts down; getMin reads index 0. insert/extract are O(log n), getMin is O(1).

insert(x):    append x; while x < parent: swap up
extractMin(): m = arr[0]; arr[0] = arr.pop(); sift down; return m