Implementing a Min-Priority Queue in Rust

Priority queues are fundamental data structures used in numerous algorithms, from shortest path calculations (like Dijkstra's algorithm) to task scheduling. They efficiently allow you to retrieve the element with the highest (or lowest) priority. This challenge focuses on implementing a min-priority queue in Rust, where the element with the smallest value is always considered the highest priority.

Problem Description

Your task is to implement a min-priority queue data structure in Rust. This structure should support the following operations:

• new(): Creates an empty priority queue.
• push(item): Inserts an item into the priority queue.
• pop(): Removes and returns the item with the smallest value from the priority queue. If the queue is empty, it should return None.
• peek(): Returns a reference to the item with the smallest value without removing it. If the queue is empty, it should return None.
• is_empty(): Returns true if the priority queue is empty, false otherwise.
• len(): Returns the number of elements in the priority queue.

The priority queue should be generic over the type of items it stores, as long as those items can be ordered (i.e., implement the Ord trait). You will likely want to leverage Rust's standard library for efficient implementation.

Examples

Example 1:

Input:
let mut pq = PriorityQueue::new();
pq.push(3);
pq.push(1);
pq.push(4);
pq.push(1);
pq.push(5);
pq.push(9);

Output:
pq.pop() -> Some(1)
pq.pop() -> Some(1)
pq.pop() -> Some(3)
pq.pop() -> Some(4)
pq.pop() -> Some(5)
pq.pop() -> Some(9)
pq.pop() -> None

Explanation: The elements are inserted in arbitrary order. pop() consistently returns the smallest available element until the queue is empty.

Example 2:

Input:
let mut pq: PriorityQueue<String> = PriorityQueue::new();
pq.push("banana".to_string());
pq.push("apple".to_string());
pq.push("cherry".to_string());

Output:
pq.peek() -> Some(&"apple")
pq.pop() -> Some("apple".to_string())
pq.pop() -> Some("banana".to_string())
pq.is_empty() -> false
pq.pop() -> Some("cherry".to_string())
pq.is_empty() -> true

Explanation: Demonstrates using String as the item type and the peek() operation. Lexicographical order determines priority.

Example 3: Edge Cases

Input:
let mut pq: PriorityQueue<i32> = PriorityQueue::new();

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

pq.push(10);
pq.push(5);
pq.pop() -> Some(5)
pq.len() -> 1
pq.push(20);
pq.pop() -> Some(10)
pq.pop() -> Some(20)
pq.pop() -> None

Explanation: Tests the behavior of an empty queue and a queue after multiple pushes and pops.

Constraints

• The priority queue must be generic, accepting any type T that implements std::cmp::Ord.
• The implementation should be efficient. Aim for O(log n) time complexity for push and pop operations, where n is the number of elements in the queue. peek, is_empty, and len should be O(1).
• You are encouraged to use Rust's standard library collections if they aid in achieving these goals.

Notes

Consider using a binary heap as the underlying data structure. Rust's standard library provides std::collections::BinaryHeap, which is a max-heap by default. You might need to adapt it or use a wrapper to achieve a min-heap. Think about how Ord is used for comparisons and how to reverse the ordering if necessary.