Implementing a Priority Queue in Rust

Priority queues are essential data structures for scenarios where elements need to be processed in order of their priority. This challenge asks you to implement a priority queue in Rust using a binary heap, a common and efficient choice for this purpose. A well-implemented priority queue will allow for efficient insertion and retrieval of the highest-priority element.

Problem Description

You are tasked with creating a PriorityQueue struct in Rust that implements a priority queue using a binary heap. The priority queue should support the following operations:

• new(): Creates a new, empty priority queue.
• push(priority: i32, value: String): Inserts a new element into the queue with the given priority and value. Lower priority values represent higher priority (e.g., 1 is higher priority than 2).
• pop(): Removes and returns the element with the highest priority (smallest priority value) from the queue. Returns None if the queue is empty.
• peek(): Returns a reference to the element with the highest priority without removing it. Returns None if the queue is empty.
• is_empty(): Returns true if the queue is empty, false otherwise.
• len(): Returns the number of elements in the queue.

The underlying data structure for the priority queue should be a BinaryHeap from the Rust standard library. You'll need to define a custom struct to be stored in the heap that holds both the priority and the value. The BinaryHeap will automatically order elements based on the Ord implementation of your custom struct. Since we want lower priority values to be considered "higher" priority, you'll need to reverse the ordering.

Examples

Example 1:

Input:
pq = PriorityQueue::new();
pq.push(3, "Task C".to_string());
pq.push(1, "Task A".to_string());
pq.push(2, "Task B".to_string());

Output:
pq.pop() == Some(("Task A".to_string(), 1))
pq.pop() == Some(("Task B".to_string(), 2))
pq.pop() == Some(("Task C".to_string(), 3))
pq.pop() == None

Explanation: The tasks are popped in order of priority (1, 2, 3).

Example 2:

Input:
pq = PriorityQueue::new();
pq.push(5, "Task E".to_string());
pq.push(5, "Task F".to_string());
pq.push(5, "Task G".to_string());

Output:
pq.pop() == Some(("Task E".to_string(), 5)) // Order of tasks with same priority is not guaranteed
pq.pop() == Some(("Task F".to_string(), 5))
pq.pop() == Some(("Task G".to_string(), 5))
pq.is_empty() == true

Explanation: Tasks with the same priority are popped in an arbitrary order.

Example 3: (Edge Case - Empty Queue)

Input:
pq = PriorityQueue::new();

Output:
pq.pop() == None
pq.peek() == None
pq.is_empty() == true
pq.len() == 0

Explanation: Handles the case where the queue is empty.

Constraints

• The priority will be an i32 and can be any integer value.
• The value will be a String.
• The number of elements pushed onto the queue will be at most 1000.
• The length of the strings will be at most 100 characters.
• The push operation should have a time complexity of O(log n), where n is the number of elements in the queue.
• The pop and peek operations should have a time complexity of O(log n).

Notes

• Use the BinaryHeap from the Rust standard library.
• You'll need to define a struct to hold the priority and value.
• Remember to reverse the ordering in your custom struct's Ord implementation to ensure that lower priority values are treated as higher priority.
• Consider using std::cmp::Reverse to simplify the ordering reversal.
• The order of elements with the same priority is not guaranteed. The BinaryHeap does not maintain a specific order among elements with equal priority.