easy +10 pts

Min Heap Class

Implement a heap-based priority queue with push, pop, peek, and size operations.

Implement a class `MinHeap` that mimics a minimum priority queue. The class must have the following methods: - `push(value)`: Add an integer `value` to the heap. - `pop()`: Remove and return the smallest element currently in the heap. If the heap is empty, return `None`. - `peek()`: Return the smallest element without removing it. If the heap is empty, return `None`. - `size()`: Return the number of elements currently in the heap. Your implementation must maintain the heap property: after every push or pop, every parent must be less than or equal to its children. You may implement the heap as a list and perform standard heap operations (bubble-up and bubble-down). Do not use Python's built-in `heapq` module; implement the logic yourself. You are also required to implement a helper function `push_pop_order(values: list) -> list` that takes a list of integers, pushes them all into a `MinHeap` instance, then pops all elements one by one and returns the resulting list (should be sorted ascending). Similarly, implement: - `peek_empty() -> None` (return the result of calling `peek()` on an empty heap) - `pop_empty() -> None` - `size_after_operations(ops: list) -> int` where `ops` is a list of integers; push each integer, then pop once, and return the final size. - `peek_after_push(value: int) -> int` (push the value and return the result of `peek()`). Make sure these functions use your `MinHeap` class and are defined in the starter code. The class definition and method signatures are given. Implement them inside the provided class and implement the helper functions as described. Your code will be tested with a series of method calls and helper function calls, and the results must match the expected order.

Constraints

Values are integers. Number of operations is at most 10^5. All heap operations should run in O(log n) time for push and pop, and O(1) for peek and size. Helper functions should operate within the same bounds.

Example

>>> h = MinHeap()
>>> h.push(5)
>>> h.push(3)
>>> h.push(8)
>>> h.peek()
3
>>> h.pop()
3
>>> h.pop()
5
>>> h.size()
1
>>> push_pop_order([5,3,8,1])
[1,3,5,8]
>>> peek_after_push(7)
7
>>> size_after_operations([1,2,3])
2
10 points ~15 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

Use a list to store the heap. The children of index i are at 2*i+1 and 2*i+2.
After pushing, bubble the new element up by swapping with its parent while it is smaller.
After popping the root, move the last element to the root and bubble it down by swapping with the smaller child.
For the helper functions, simply instantiate MinHeap and call its methods.
Python 3
All tests passed!
Test Results
Press Ctrl+Enter or click Run Tests to execute your code.