Mastering Python's Heapq Module: Priority Queue Implementation

The heapq module in Python provides an implementation of the heap queue algorithm, also known as the priority queue algorithm. This module is invaluable for efficiently managing data where elements need to be retrieved in a specific order, typically from smallest to largest. This challenge will test your understanding of heapq's core functionalities by asking you to implement common priority queue operations.

Problem Description

Your task is to simulate the behavior of a priority queue using Python's heapq module. You will be given a sequence of operations to perform on an initially empty heap. These operations will include adding elements, retrieving and removing the smallest element, and examining the smallest element without removing it.

You need to implement a class, let's call it PriorityQueue, that encapsulates these operations. The class should maintain an internal heap structure using heapq.

Key Requirements:

1. Initialization: The PriorityQueue should be initialized as an empty data structure.
2. push(item): Adds an item to the priority queue.
3. pop(): Removes and returns the smallest item from the priority queue. If the queue is empty, it should raise an IndexError.
4. peek(): Returns the smallest item from the priority queue without removing it. If the queue is empty, it should raise an IndexError.
5. is_empty(): Returns True if the priority queue is empty, and False otherwise.

Expected Behavior:

The priority queue should always maintain the heap property, meaning the smallest element is always at the root (index 0). Operations should reflect the standard behavior of a min-heap priority queue.

Edge Cases:

• Attempting to pop() or peek() from an empty queue.
• Pushing duplicate elements.
• Pushing elements of different but comparable types (e.g., integers and floats).

Examples

Example 1:

Input Operations:
pq = PriorityQueue()
pq.push(3)
pq.push(1)
pq.push(4)
print(pq.peek())
print(pq.pop())
pq.push(2)
print(pq.pop())
print(pq.is_empty())
print(pq.pop())
print(pq.is_empty())

Output:
1
1
2
False
3
True

Explanation:

1. pq = PriorityQueue(): An empty priority queue is created.
2. pq.push(3): Heap: [3]
3. pq.push(1): Heap: [1, 3]
4. pq.push(4): Heap: [1, 3, 4]
5. print(pq.peek()): Returns 1 (smallest element). Heap remains [1, 3, 4].
6. print(pq.pop()): Returns 1. Heap becomes [3, 4] after rearrangement.
7. pq.push(2): Heap: [2, 4, 3] (after push and heapify).
8. print(pq.pop()): Returns 2. Heap becomes [3, 4].
9. print(pq.is_empty()): Returns False.
10. print(pq.pop()): Returns 3. Heap becomes [4].
11. print(pq.is_empty()): Returns False.
12. print(pq.pop()): Returns 4. Heap becomes [].
13. print(pq.is_empty()): Returns True.

Example 2:

Input Operations:
pq = PriorityQueue()
try:
    pq.pop()
except IndexError as e:
    print(e)
try:
    pq.peek()
except IndexError as e:
    print(e)
pq.push(5)
pq.push(5)
pq.push(1)
print(pq.pop())
print(pq.pop())

Output:
Queue is empty
Queue is empty
1
5

Explanation:

1. The first two pop() and peek() calls on an empty queue correctly raise IndexError with the message "Queue is empty".
2. Elements 5, 5, and 1 are pushed. The heap might look something like [1, 5, 5].
3. The first pop() returns 1.
4. The second pop() returns 5.

Constraints

• The number of push operations will not exceed 1000.
• The number of pop and peek operations will not exceed 1000.
• Items pushed into the queue will be integers or floats.
• The time complexity for push and pop operations should be O(log n), where n is the number of elements in the queue. The time complexity for peek and is_empty should be O(1).

Notes

• Remember that heapq functions operate on standard Python lists.
• When implementing pop and peek, ensure you handle the empty queue scenario gracefully by raising an IndexError.
• Consider how heapq internally manages the heap structure to ensure correctness when elements are added or removed.