Priority Queue

Problem

Write a solution function that processes a series of queries using a priority queue and returns the results.

Query Information

• x (x is a natural number):
  Insert x into the priority queue.
  No changes are made to the result.
• 0:
  Remove the smallest number from the priority queue and add it to the result. If the priority queue is empty, add 0 to the result instead.

Concept Explanation

A standard queue operates on a First-In-First-Out (FIFO) principle.
Refer to "DailyAlgo: Queue".

However, a priority queue outputs elements based on their priority, not their insertion order.
A priority queue supports the following operations:

1. push X: Insert element X into the queue.
2. pop: Remove and return the element with the highest priority.

To define a priority queue, you must specify the elements and the criteria for their priority.

For example, consider a priority queue of natural numbers where smaller numbers have higher priority:

(push 4), (push 10), (push 7), (pop), (pop), (push 5), (pop), (push 15), (pop)

If implemented as a descending-sorted array, the operations can be visualized as follows:

• On push, insert the element and sort the array in descending order. The smallest number (highest priority) is placed at the end.
• On pop, remove the last element from the array.

With this approach:

• push requires sorting, resulting in a time complexity of $O(N)$.
• pop involves removing the last element, with a time complexity of $O(1)$.

Thus, for $N$ queries, the total time complexity is $O(N^2)$.

Using a heap to implement the priority queue reduces the overall complexity to $O(N\log N)$.

Heap Definition

1. A heap is a complete binary tree.
2. Every node is greater than or equal to its children in priority.

The following examples are not heaps:

1. The first does not maintain a complete binary tree structure.
2. The second violates the priority rule.

Consider the following valid heap:

Push Operation

To push 13:

1. Add 13 as the last node to maintain the complete binary tree structure.
2. Swap it with its parent if it has a higher priority.
3. Repeat until the root or a parent with higher priority is reached.

Pop Operation

To pop:

1. Remove the root node (highest priority).
2. Replace it with the last node.
3. Swap with the child of lower priority until reaching a leaf or maintaining heap properties.

Using a heap, both push and pop operations have a time complexity of $O(log N)$, and the total complexity for $N$ queries is O(N log N)

Constraints

• Each element in queries is an integer between 0 and 10,000 inclusive.
• The length of queries is at most 100,000.
• queries contains at least one 0.

Test Cases

Explanation for Test Case 1

• Same as the example provided above.

Explanation for Test Case 2

Explanation for Test Case 3