A min-heap that always hands back the smallest

mediumData Structures+250 XPPractice

When work arrives out of order but must be processed smallest-first — earliest deadline, closest timestamp, cheapest route — a heap beats re-sorting an array on every insert.

Implement a MinHeap class holding numbers. It is constructed with no arguments and starts empty. push(value) inserts a number and returns the new size. pop() removes and returns the smallest number currently held, or returns undefined when the heap is empty. peek() returns the smallest number without removing it, or undefined when empty. size() returns how many numbers are held.

Only the sequence of values coming out of pop() is specified; the internal arrangement is yours to choose. Duplicate values are allowed and each must come out separately.

Examples

const h = new MinHeap();
[5, 1, 4, 2, 8].forEach((v) => h.push(v));
h.peek();  // 1
h.pop();   // 1
h.pop();   // 2
h.pop();   // 4

Pop drains in ascending order no matter the push order.

const h = new MinHeap();
h.push(5); h.push(3);
h.pop();   // 3
h.push(1); h.push(4);
h.pop();   // 1 — interleaved pushes and pops are fine

What it has to do

Repeated pop() calls return the values in ascending order.
Duplicate values are each returned separately.
peek() returns the smallest value without removing it.
pop() and peek() return undefined on an empty heap.
Pushing and popping can be interleaved in any order.

Notes

push and pop are O(log n); peek is O(1). Draining n items is O(n log n), the price of staying sorted on the fly instead of up front.
A heap in an array uses the parent/child index formulas (i - 1) / 2 and 2i + 1, 2i + 2. No node pointers are needed — the array is the structure.

Asked atGoogleAmazon

Stuck? The javascript course covers everything this challenge needs.

Try it yourself· Edit the code, then press Run

Loading playground...

5 tests · +250 XP

Discussion

No comments yet. Be the first to say something.

All challenges107 / 150