Scala Tutorial - Learn How To Use Scala's Mutable PriorityQueue
Overview
In this tutorial, we will learn how to use Scala's Mutable PriorityQueue to perform common operations such as initialize a PriorityQueue, specify ordering of elements, enqueue and dequeue elements and create an empty PriorityQueue.
And, don't forget to review the Data Structures tutorial before delving into Scala's Immutable and Mutable collections.
More advanced functions such as aggregate, fold, reduce, map, flatMap etc on the Mutable PriorityQueue will be discussed in Chapter 8 on Collection Functions.
What is a PriorityQueue?
As per Wikipedia, a PriorityQueue is similar to a queue data structure except that elements added to the queue are associated with a priority. This priority is then used to determine which elements get dequeued or removed from the queue.
As per the Scala Documentation, a mutable PriorityQueue is implemented using a heap data structure and only the method dequeue and dequeueAll will return the elements in their priority order.
Steps
1. How to declare a case class to represent Donut object
The code below shows how to declare a case class to represent Donut object.
println("Step 1: How to declare a case class to represent Donut object")
case class Donut(name: String, price: Double)
2. How to declare a function which defines the ordering of a PriorityQueue of Donut objects
The code below shows how to declare a function which defines the ordering of a PriorityQueue of Donut objects
println("\nStep 2: How to declare a function which defines the ordering of a PriorityQueue of Donut objects")
def donutOrder(d: Donut) = d.price
NOTE:
- If you need to order by the lowest element, you can -d.price
3. How to initialize a PriorityQueue of Donut objects and specify the Ordering
The code below shows how to initialize a PriorityQueue of Donut objects and specify the Ordering
println("\nStep 3: How to initialize a PriorityQueue of Donut objects and specify the Ordering")
import scala.collection.mutable.PriorityQueue
val priorityQueue1: PriorityQueue[Donut] = PriorityQueue(
Donut("Plain Donut", 1.50),
Donut("Strawberry Donut", 2.0),
Donut("Chocolate Donut", 2.50))(Ordering.by(donutOrder))
println(s"Elements of priorityQueue1 = $priorityQueue1")
You should see the following output when you run your Scala application in IntelliJ:
Step 3: How to initialize a PriorityQueue of Donut objects and specify the Ordering
Elements of priorityQueue1 = PriorityQueue(Donut(Chocolate Donut,2.5), Donut(Plain Donut,1.5), Donut(Strawberry Donut,2.0))
4. How to add an element to PriorityQueue using enqueue function
The code below shows how to add an element to PriorityQueue using enqueue function.
println("\nStep 4: How to add an element to PriorityQueue using enqueue function")
priorityQueue1.enqueue(Donut("Vanilla Donut", 1.0))
println(s"Elements of priorityQueue1 after enqueue function is called = $priorityQueue1")
You should see the following output when you run your Scala application in IntelliJ:
Step 4: How to add an element to PriorityQueue using enqueue function
Elements of priorityQueue1 after enqueue function is called = PriorityQueue(Donut(Chocolate Donut,2.5), Donut(Plain Donut,1.5), Donut(Strawberry Donut,2.0), Donut(Vanilla Donut,1.0))
5. How to add an element to PriorityQueue using +=
The code below shows how to add an element to PriorityQueue using +=.
println("\nStep 5: How to add an element to PriorityQueue using +=")
priorityQueue1 += (Donut("Krispy Kreme Donut", 1.0))
println(s"Elements of priorityQueue1 after enqueue function is called = $priorityQueue1")
You should see the following output when you run your Scala application in IntelliJ:
Step 5: How to add an element to PriorityQueue using +=
Elements of priorityQueue1 after enqueue function is called = PriorityQueue(Donut(Chocolate Donut,2.5), Donut(Plain Donut,1.5), Donut(Strawberry Donut,2.0), Donut(Vanilla Donut,1.0), Donut(Krispy Kreme Donut,1.0))
6. How to remove an element from PriorityQueue using the dequeue function
The code below shows how to remove an element from PriorityQueue using the dequeue function.
println("\nStep 6: How to remove an element from PriorityQueue using the dequeue function")
val donutDequeued: Donut = priorityQueue1.dequeue()
println(s"Donut element dequeued = $donutDequeued")
println(s"Elements of priorityQueue1 after dequeued function is called = $priorityQueue1")
You should see the following output when you run your Scala application in IntelliJ:
Step 6: How to remove an element from PriorityQueue using the dequeue function
Donut element dequeued = Donut(Chocolate Donut,2.5)
Elements of priorityQueue1 after dequeued function is called = PriorityQueue(Donut(Strawberry Donut,2.0), Donut(Plain Donut,1.5), Donut(Krispy Kreme Donut,1.0), Donut(Vanilla Donut,1.0))
NOTE:
- The donut element with the highest price in the queue was the first one that was removed.
7. How to initialize an empty PriorityQueue
The code below shows how to initialize an empty PriorityQueue.
println("\nStep 7: How to initialize an empty PriorityQueue")
val emptyPriorityQueue: PriorityQueue[String] = PriorityQueue.empty[String]
println(s"Empty emptyPriorityQueue = $emptyPriorityQueue")
You should see the following output when you run your Scala application in IntelliJ:
Step 7: How to initialize an empty PriorityQueue
Empty emptyPriorityQueue = PriorityQueue()
Summary
In this tutorial, we went over the following:
- How to use a case class to represent an object
- How to declare a function which defines the ordering of a PriorityQueue
- How to initialize a PriorityQueue and specify the ordering of its elements
- How to add an element to PriorityQueue using enqueue function
- How to add an element to PriorityQueue using +=
- How to remove an element from PriorityQueue using the dequeue function
- How to initialize an empty PriorityQueue
Tip
- Don't forget to review Chapter 8 on Collection Functions where we will go over the rich suite of functions exposed on collections such as aggregate, collect, fold, reduce, map, flatMap, scan, partition etc
- Scala's documentation on mutable PriorityQueue.
Source Code
The source code is available on the allaboutscala GitHub repository.
What's Next
In the next tutorial, I will show you how to use Scala's Mutable Set.
