Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

data structures
hash map
insertion
deletion
time complexity

How to use the priority_queue crate in Rust

Educative Answers Team

The priority_queue crate in Rust provides an implementation of a priority queue based on a hashmap. Every item (or key) that is inserted is mapped to a hash value, using hashing, and a priority is assigned to it. In this way, a hashmap stores the data in the form of key-value pairs.

The following commonly used functions are provided in this crate:

  1. push(item, priority): An item is inserted in the priority queue that has the specified priority. The key should be of a type that implements the Hash and Eq traits because a hashmap is being used under the hood.

  2. pop(): The item with the highest priority is removed from the queue and returned. The item returned is of type Option. If the queue is empty, None is returned.

  3. peek(): The item with the highest priority is only returned without being removed.

  4. change_priority(item, new_priority): The item is looked up in the hashmap and, if it is found, the new priority is assigned to it and the old priority is returned; otherwise, the function returns None.

Code

use priority_queue::PriorityQueue;

fn main() {
  let mut q = PriorityQueue::new();

  // Add elements to an empty queue:
  assert!(q.is_empty());
  q.push("Maths", 10);
  q.push("Physics", 5);
  q.push("Chemistry", 15);

  // Check if Chemistry has the highest priority:
  assert_eq!(q.peek(), Some((&"Chemistry", &15)));

  // Give highest priority to Maths:
  q.change_priority("Maths", 20);

  // Check if Maths has the highest priority:
  assert_eq!(q.peek(), Some((&"Maths", &20)));
}

RELATED TAGS

data structures
hash map
insertion
deletion
time complexity
Copyright ©2022 Educative, Inc. All rights reserved
RELATED COURSES

View all Courses

Keep Exploring