Implement a Min-Priority Queue Without a Library Heap
Company: Amazon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
## Problem
Implement a min-priority queue from first principles. The queue stores integer values, preserves duplicates, and must support insertion, inspection, removal, and size queries without using a built-in heap or priority-queue implementation.
## Function Contract
Implement `run_priority_queue(operations)` and return the outputs from `PEEK`, `POP`, and `SIZE` operations as strings.
## Rules
- `["PUSH", value]` inserts one occurrence and produces no output.
- `["PEEK"]` emits the minimum value without removing it, or `"EMPTY"` when the queue is empty.
- `["POP"]` removes and emits the minimum value, or emits `"EMPTY"` when the queue is empty.
- `["SIZE"]` emits the current number of stored values.
- Do not use a language-provided heap, priority queue, ordered multiset, or full-array sort after each insertion.
## Constraints
- `1 <= len(operations) <= 200000`.
- Inserted values are integers in `[-10^9, 10^9]`.
- Target `O(log n)` time for `PUSH` and `POP`, and `O(1)` for `PEEK` and `SIZE`.
## Examples
```text
operations = [["PUSH", 7], ["PUSH", 2], ["PUSH", 2], ["PEEK"], ["POP"], ["SIZE"]]
output = ["2", "2", "2"]
```
Overview: Implement a min-priority queue without a library heap. Support duplicate integers, push, peek, pop, and size operations efficiently while returning deterministic results for empty-queue queries.
Process a sequence of priority-queue operations using a binary min-heap that you build yourself. Each operation is one of ["PUSH", value], ["PEEK"], ["POP"], or ["SIZE"]. PUSH inserts the integer value and produces no output. PEEK appends the minimum value as a string, or "EMPTY" when the queue is empty. POP removes and appends the minimum value as a string, or appends "EMPTY" when the queue is empty. SIZE appends the current number of stored values as a string. Return all produced strings in operation order. Preserve duplicate values. Do not use a built-in heap, priority queue, ordered multiset, or a full sort.
Constraints
- 1 <= len(operations) <= 200000.
- Each operation is PUSH value, PEEK, POP, or SIZE.
- Every pushed value is an integer in [-1000000000, 1000000000].
- Duplicate values must be preserved.
- Do not use a built-in heap, priority queue, ordered multiset, or full sorting of stored values.
Examples
Input: ([['PUSH', 7], ['PUSH', 2], ['PUSH', 2], ['PEEK'], ['POP'], ['SIZE']],)
Expected Output: ['2', '2', '2']
Explanation: The minimum is 2, one copy is popped, and two values remain.
Input: ([['PEEK'], ['POP'], ['SIZE']],)
Expected Output: ['EMPTY', 'EMPTY', '0']
Explanation: Queries against an empty queue use the required sentinel and report size zero.
Hints
- Use an array where the children of index i are 2*i+1 and 2*i+2.
- A push bubbles upward; removing the root moves the last element down through the smaller child.