Implement a Min-Priority Queue Without a Library Heap

Description

Design a min-priority queue data structure from scratch without using any built-in heap or priority queue libraries (such as Python's heapq, Java's PriorityQueue, or C++'s std::priority_queue).

The priority queue stores integers, supports duplicate values, and must provide standard priority queue operations with optimal time complexities.

Implement the MinPriorityQueue class with the following methods:

• push(val: int) -> None: Inserts integer val into the priority queue.
• peek() -> int | None: Returns the minimum element currently in the queue without removing it. If the queue is empty, returns None.
• pop() -> int | None: Removes and returns the minimum element from the queue. If the queue is empty, returns None.
• size() -> int: Returns the current number of elements stored in the queue.

Interface

class MinPriorityQueue:
    def __init__(self):
        pass

    def push(self, val: int) -> None:
        pass

    def peek(self) -> int | None:
        pass

    def pop(self) -> int | None:
        pass

    def size(self) -> int:
        pass

Example

pq = MinPriorityQueue()
pq.push(5)
pq.push(3)
pq.push(8)
pq.push(3) # duplicates are supported

print(pq.peek()) # returns 3
print(pq.size()) # returns 4

print(pq.pop())  # returns 3
print(pq.pop())  # returns 3
print(pq.pop())  # returns 5
print(pq.size()) # returns 1

print(pq.pop())  # returns 8
print(pq.pop())  # returns None (queue is empty)
print(pq.peek()) # returns None

Constraints

• Total operations called across push, peek, pop, and size: up to 2 * 10^5.
• Values inserted: -10^9 <= val <= 10^9.
• push must run in O(log n) time.
• pop must run in O(log n) time.
• peek and size must run in O(1) time.