Min-Heap From Scratch
Problem
Implement a min-heap on top of a plain array, without any library priority queue. It is driven by a list of operations: ops[i] is "push" (insert vals[i]), "pop" (remove and report the smallest value) or "peek" (report the smallest value without removing it). For "pop" and "peek", vals[i] is 0 and ignored.
Return the reported values in order. When "pop" or "peek" runs on an empty heap, report -1.
Example 1
- Input:
- ops = ["push", "push", "push", "peek", "pop", "pop", "peek"], vals = [5, 2, 8, 0, 0, 0, 0]
- Output:
- [2, 2, 5, 8]
After pushing 5, 2, 8 the minimum is 2 (peek). pop removes 2, then pop removes 5, and peek sees 8.
Example 2
- Input:
- ops = ["pop", "push", "peek"], vals = [0, 4, 0]
- Output:
- [-1, 4]
Constraints
- 1 ≤ ops.length ≤ 10^5
- 0 ≤ vals[i] ≤ 10^5 for "push"
- Library heaps (heapq, priority queues) are not allowed.
Hint
Show the first hint
Store the heap as an array where the children of index i are 2i + 1 and 2i + 2, and the parent is (i - 1) // 2.
Walkthrough
How to approach it
01Clarify before coding
- Can I use heapq / a library priority queue? No, the point is to build the structure.
- What do pop and peek report on an empty heap? -1, which is safe because pushed values are non-negative.
- Are duplicates allowed? Yes.
02Brute force
Keep an unsorted list: push appends, pop and peek scan for the minimum (pop also removes it).
Cost: O(1) push but O(n) pop and peek, so O(n²) for 10^5 operations. A sorted list flips the costs (O(n) push from shifting).
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.