Implement a Priority Queue from Scratch

Problem Implement a priority queue from scratch, without using the language's built-in heap or priority-queue library, supporting insertion and extraction of the highest-priority element.

Input / Output

• Input: a sequence of operations — insert(x), extractMin() (or extractMax()), peek(), size().
• Output: extract removes and returns the minimum (or maximum) element; peek returns it without removing; both error or return a sentinel on an empty queue.

Constraints

• Up to ~10^6 operations, so each must run in O(log n) or better — a sorted-array insert at O(n) per call is not acceptable.
• Must handle duplicate priorities and grow without a fixed capacity limit.
• No library heap; the underlying array and sift logic are the deliverable.

Example

• insert(5), insert(1), insert(3) → peek() = 1; extractMin() → 1; extractMin() → 3; peek() → 5.
• insert(2), insert(2), extractMin() → 2 — duplicates must not corrupt the heap order.