Priority Queue Introduction and Concept in DSA Rust - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output of this Rust priority queue code?

Consider the following Rust code using a max-heap priority queue. What will be printed?

DSA Rust

use std::collections::BinaryHeap;

fn main() {
    let mut pq = BinaryHeap::new();
    pq.push(10);
    pq.push(5);
    pq.push(20);
    pq.push(1);

    while let Some(val) = pq.pop() {
        print!("{} ", val);
    }
}

A 1 5 10 20

B 20 10 5 1

C 10 20 5 1

D 5 1 10 20

💡 Hint

Remember that Rust's BinaryHeap is a max-heap by default, so the largest element comes out first.

The BinaryHeap in Rust is a max-heap, so popping elements returns the largest first. The elements pushed are 10, 5, 20, and 1. Popping them prints 20, then 10, then 5, then 1.

🧠 Conceptual

intermediate

Which property does a priority queue always maintain?

Choose the property that a priority queue guarantees about its elements.

A Elements are grouped by their priority but not ordered.

B Elements are always sorted in ascending order internally.

C Elements are stored in the order they were inserted.

D The element with the highest priority is always accessible first.

💡 Hint

Think about what 'priority' means in a priority queue.

A priority queue always allows quick access to the element with the highest priority (largest or smallest depending on implementation). It does not guarantee full sorting or insertion order.

🔧 Debug

advanced

What error does this Rust priority queue code produce?

Analyze the following Rust code snippet. What error will it cause when compiled?

DSA Rust

use std::collections::BinaryHeap;

fn main() {
    let mut pq = BinaryHeap::new();
    pq.push("apple");
    pq.push("banana");
    pq.push(10);
}

A Type mismatch error because of mixed types pushed into the heap.

B No error; code compiles and runs fine.

C Runtime panic due to invalid element comparison.

D Syntax error due to missing semicolon.

💡 Hint

Rust's BinaryHeap requires all elements to be of the same type and comparable.

The code tries to push both &str and integer types into the same BinaryHeap. Rust requires all elements to have the same type and implement Ord. This causes a compile-time type mismatch error.

🚀 Application

advanced

How many elements remain after these priority queue operations?

Given a priority queue initially empty, the following operations are performed:

• push 15
• push 30
• pop
• push 10
• pop

How many elements remain in the priority queue?

A 3

B 2

C 1

D 0

💡 Hint

Track the queue size after each operation carefully.

Operations:
push 15 → size 1
push 30 → size 2
pop (removes 30) → size 1
push 10 → size 2
pop (removes 15) → size 1
So, 1 element remains.

❓ Predict Output

expert

What is the output of this Rust code using a min-heap with Reverse wrapper?

Rust's BinaryHeap is a max-heap by default. This code uses std::cmp::Reverse to simulate a min-heap. What will it print?

DSA Rust

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn main() {
    let mut pq = BinaryHeap::new();
    pq.push(Reverse(40));
    pq.push(Reverse(10));
    pq.push(Reverse(30));
    pq.push(Reverse(20));

    while let Some(Reverse(val)) = pq.pop() {
        print!("{} ", val);
    }
}

A 10 20 30 40

B 40 30 20 10

C 20 10 40 30

D 30 40 10 20

💡 Hint

Reverse reverses the order, so the smallest element comes out first.

Using Reverse wraps values so BinaryHeap treats them as reversed order, effectively making it a min-heap. Popping returns 10, 20, 30, then 40.

Practice

1. What is the main feature of a Priority Queue compared to a regular queue?

easy

A. It only stores elements of the same value

B. Elements are always dequeued in the order they were inserted

C. Elements are dequeued based on priority, not just order of insertion

D. It does not allow duplicate elements

Solution

1. Step 1: Understand queue behavior

   A regular queue removes elements in the order they were added (FIFO).

2. Step 2: Understand priority queue behavior

   A priority queue removes elements based on their priority, not just insertion order.

3. Final Answer:

   Elements are dequeued based on priority, not just order of insertion -> Option C

4. Quick Check:

   Priority Queue = Priority-based removal [OK]

Hint: Priority queue removes highest priority first, not oldest [OK]

Common Mistakes:

• Confusing priority queue with FIFO queue
• Thinking priority queue sorts elements permanently
• Assuming priority queue disallows duplicates

2. Which of the following is the correct way to create a max-heap priority queue in Rust using std::collections::BinaryHeap?

easy

A. let mut pq = std::collections::BinaryHeap::min_heap();

B. let mut pq = std::collections::BinaryHeap::with_capacity(10i32);

C. let mut pq = std::collections::BinaryHeap::default(10);

D. let mut pq = std::collections::BinaryHeap::new();

Solution

1. Step 1: Recall Rust BinaryHeap creation

   The standard way to create a max-heap priority queue is using BinaryHeap::new().

2. Step 2: Check other options

   with_capacity(10i32) type mismatch (usize expected); default(10) invalid arguments; min_heap() does not exist.

3. Final Answer:

   let mut pq = std::collections::BinaryHeap::new(); -> Option D

4. Quick Check:

   BinaryHeap::new() creates max-heap [OK]

Hint: Use BinaryHeap::new() for max-heap priority queue [OK]

Common Mistakes:

• Using with_capacity with i32 instead of usize
• Passing arguments to default()
• Using non-existent min_heap() method

3. What will be the output of the following Rust code using a priority queue?

use std::collections::BinaryHeap;

fn main() {
    let mut pq = BinaryHeap::new();
    pq.push(10);
    pq.push(5);
    pq.push(20);
    while let Some(val) = pq.pop() {
        print!("{} ", val);
    }
}

medium

A. 20 10 5

B. 5 20 10

C. 10 5 20

D. 5 10 20

Solution

1. Step 1: Understand BinaryHeap behavior

   Rust's BinaryHeap is a max-heap by default, so pop() returns the largest element first.

2. Step 2: Trace the pop order

   Inserted values: 10, 5, 20. Popping returns 20, then 10, then 5.

3. Final Answer:

   20 10 5 -> Option A

4. Quick Check:

   Max-heap pop order = descending [OK]

Hint: BinaryHeap pops largest first, so output is descending [OK]

Common Mistakes:

• Assuming pop returns elements in insertion order
• Thinking BinaryHeap is min-heap by default
• Mixing up push and pop order

4. Identify the error in this Rust code that tries to create a min-heap priority queue:

use std::collections::BinaryHeap;

fn main() {
    let mut pq = BinaryHeap::new();
    pq.push(3);
    pq.push(1);
    pq.push(2);
    while let Some(val) = pq.pop() {
        println!("{}", val);
    }
}

medium

A. BinaryHeap does not support min-heap by default

B. pq.push() method does not exist

C. pop() returns elements in insertion order

D. println! macro is used incorrectly

Solution

1. Step 1: Check BinaryHeap default behavior

   Rust's BinaryHeap is a max-heap by default, so it does not create a min-heap without extra work.

2. Step 2: Verify code correctness

   push() and pop() methods exist and println! is correct; the issue is the heap type.

3. Final Answer:

   BinaryHeap does not support min-heap by default -> Option A

4. Quick Check:

   BinaryHeap default = max-heap, no min-heap [OK]

Hint: BinaryHeap is max-heap by default; min-heap needs wrapper [OK]

Common Mistakes:

• Assuming BinaryHeap is min-heap by default
• Thinking push() or pop() are missing
• Misreading println! syntax

5. You want to implement a task scheduler in Rust that always runs the highest priority task first. Which approach correctly uses a priority queue to achieve this?

use std::collections::BinaryHeap;

struct Task {
    priority: i32,
    name: String,
}

fn main() {
    let mut pq = BinaryHeap::new();
    pq.push(Task { priority: 2, name: String::from("Clean") });
    pq.push(Task { priority: 5, name: String::from("Cook") });
    pq.push(Task { priority: 1, name: String::from("Shop") });

    while let Some(task) = pq.pop() {
        println!("{}", task.name);
    }
}

What must you do to make this code work as intended?

hard

A. Use a Vec<Task> instead of BinaryHeap

B. Implement Ord and Eq traits for Task to order by priority

C. Change priority to u32 type

D. Replace pop() with peek() in the loop

Solution

1. Step 1: Understand BinaryHeap requirements

   BinaryHeap requires elements to implement Ord and Eq to compare and order them.

2. Step 2: Check code for ordering

   Task struct has no ordering traits implemented, so BinaryHeap cannot order tasks by priority.

3. Step 3: Correct approach

   Implement Ord and Eq for Task to order by priority, so highest priority pops first.

4. Final Answer:

   Implement Ord and Eq traits for Task to order by priority -> Option B

5. Quick Check:

   BinaryHeap needs Ord/Eq for custom types [OK]

Hint: Custom types need Ord/Eq traits for BinaryHeap ordering [OK]

Common Mistakes:

• Using Vec instead of priority queue
• Changing data type without ordering
• Using peek() instead of pop() to remove elements