Min Heap

Track: Data structures. 6 stages. Languages: Go, Python, JavaScript, Rust.

Build a structure that always hands back the smallest value you are holding, no matter what order you pushed things in. Keep every value in a flat array you manage yourself. Each value must be no bigger than either of the two values below it, so the smallest value always sits at the very front. Implement New() (no size limit), Push(v), Pop() -> (v, ok), Peek() -> (v, ok), and Len() -> int using your language's names. Values are plain whole numbers: there is no separate priority, the value itself is the priority. Use only the standard library, not a ready-made priority queue. Your heap receives one call at a time. For help with the ideas, read the notes.

Where it is used

• Go's runtime keeps a program's timers (from time.After, timeouts, and so on) in a heap ordered by when they fire, so it always knows which one is next.
• libevent, an event library for network servers, keeps pending timeouts in a min heap, so finding the next timeout takes the same small time however many are waiting.
• Job schedulers and route finders use a heap as a priority queue. Python's heapq and Go's container/heap exist for this.

If your heap picks the wrong child on the way down, values come out in the wrong order, and in a timer system the wrong timeout fires first.

Stages

mh1: hello: push then pop (very easy)

Push a few values, then pop them all. Every pop must return the smallest value you are still holding, not the one you pushed last and not the one you pushed first. Example: Push(5), Push(2), Push(8), then Pop() -> (2, true), Pop() -> (5, true), Pop() -> (8, true).

The tester will verify: Pop returns values from smallest to largest, not in push order and not in reverse push order.

mh2: moving up multiple levels, duplicates, and zero (easy)

A value you push can need to move up past more than one step to reach the front. Two equal values both stay, as separate values. A real 0 is a found value, never a "not found" signal, and Peek must not remove anything.

push 7, 3:     [7, 3]
push 3 again:  [7, 3, 3]        (small enough already, stays where it lands)
push 0:        [0, 3, 3, 7]     (0 moves all the way to the front)

Example: Push(7), Push(3), Push(3), Push(0), Peek() -> (0, true), then Pop() three times returns 0, 3, 3.

The tester will verify: a value that needs to move up more than one step still ends up in front, both equal values survive, a real 0 is found and not treated as missing, and Peek leaves the heap unchanged.

mh3: pop order and Len (medium)

When you pop, take your last remaining value, put it at the front, and let it settle down to the right place. Removing a value some other way, such as shifting everything over by one slot, breaks the order for the rest. Len must count exactly what is left, checked after every single push and pop. Example: push 1, 2, 4, 3, 5 in that order, then pop everything. Every pop must come out 1, 2, 3, 4, 5, and Len must match after each call, including when the heap is empty.

The tester will verify: popping in this order still produces the smallest value every time, and Len stays exactly right through every push and pop.

mh4: picking the smaller branch going down (medium-hard)

A value moving down after a pop has two values below it. It must always move toward the smaller of the two, never just the one on a fixed side.

      5
    /   \
   8     3      <- 3 is smaller, so 5 must move toward 3, not 8

Example: push 15 values in a fixed order, then pop them all. Every pop must still come out smallest to largest.

The tester will verify: a full drain of a deeper heap still comes out smallest to largest, which only happens if both of a value's children are checked at every step, not just one.

mh5: many pushes and pops (hard)

Keep every answer right over a long run of thousands of pushes and pops, including negative numbers, 0, and repeated values. Values can be as small as -2147483648 and as large as 2147483647. Example: push -1, the smallest possible value, the largest possible value, and 0. Peek, then pop everything back out in order. After that, run a long mix of more pushes and pops.

The tester will verify: every answer across the whole run is correct, including near the smallest and largest possible values. Do not use a negative number as an internal "empty" signal: a real negative value, including a real -1, must come back out like any other value.

mh6: push and pop speed (L2, hard)

Keep Push and Pop fast even when the heap holds many values. Keep every answer correct. Example: if our solution takes 100 ms, the limit is 150 ms. Your solution takes 140 ms, so it passes.

The tester will verify: your code takes at most 1.5 times as long as our solution in the same language, and every answer stays correct.

Rules

• Build the heap yourself over a flat array - no ready-made priority-queue/heap types (Python heapq, Go container/heap, Rust BinaryHeap, C++ std::priority_queue/make_heap/push_heap/pop_heap, Java/Kotlin PriorityQueue, Zig std.PriorityQueue, or any ordered-tree/set used in their place).
• Standard library only.

Read the Min Heap notes in the wiki