13.
Priority Queues
Written by Irina Galata, Kelvin Lau and Vincent Ngo
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
Queues are lists that maintain the order of elements using first in, first out (FIFO) ordering. A priority queue is another version of a queue. However, instead of using FIFO ordering, elements are dequeued in priority order.
A priority queue can have either a:
- Max-priority: The element at the front is always the largest.
- Min-priority: The element at the front is always the smallest.
A priority queue is especially useful when you need to identify the maximum or minimum value within a list of elements.
In this chapter, you’ll learn the benefits of a priority queue and build one by leveraging the existing queue and heap data structures that you studied in previous chapters.
Applications
Some useful applications of a priority queue include:
- Dijkstra’s algorithm: Uses a priority queue to calculate the minimum cost.
- A* pathfinding algorithm: Uses a priority queue to track the unexplored routes that will produce the path with the shortest length.
- Heap sort: Many heap sorts use a priority queue.
- Huffman coding: Useful for building a compression tree. A min-priority queue is used to repeatedly find two nodes with the smallest frequency that don’t yet have a parent node.
Priority queues have many more applications and practical uses; the list above represents only a handful.
Common operations
In Chapter 5, “Queues”, you established the following interface for queues:
interface Queue<T> {
fun enqueue(element: T): Boolean
fun dequeue(): T?
val count: Int
get
val isEmpty: Boolean
get() = count == 0
fun peek(): T?
}
Implementation
You can create a priority queue in the following ways:
// 1
abstract class AbstractPriorityQueue<T> : Queue<T> {
// 2
abstract val heap: Heap<T>
get
// more to come ...
}
// 1
override fun enqueue(element: T): Boolean {
heap.insert(element)
return true
}
// 2
override fun dequeue() = heap.remove()
// 3
override val count: Int
get() = heap.count
// 4
override fun peek() = heap.peek()
Using Comparable objects
AbstractPriorityQueue<T> implements the Queue<T> interface delegating to a Heap<T>. You can implement this using either Comparable<T> objects or a Comparator<T>. In this example, you’ll use the former.
class ComparablePriorityQueueImpl<T : Comparable<T>> :
AbstractPriorityQueue<T>() {
override val heap = ComparableHeapImpl<T>()
}
"max priority queue" example {
// 1
val priorityQueue = ComparablePriorityQueueImpl<Int>()
// 2
arrayListOf(1, 12, 3, 4, 1, 6, 8, 7).forEach {
priorityQueue.enqueue(it)
}
// 3
while (!priorityQueue.isEmpty) {
println(priorityQueue.dequeue())
}
}
---Example of max priority queue---
12
8
7
6
4
3
1
1
Using Comparator objects
Providing different Comparator<T> interface implementations allows you to choose the priority criteria.
class ComparatorPriorityQueueImpl<T>(
private val comparator: Comparator<T>
) : AbstractPriorityQueue<T>() {
override val heap = ComparatorHeapImpl(comparator)
}
"min priority queue" example {
// 1
val stringLengthComparator = object : Comparator<String> {
override fun compare(o1: String?, o2: String?): Int {
val length1 = o1?.length ?: -1
val length2 = o2?.length ?: -1
return length1 - length2
}
}
// 2
val priorityQueue = ComparatorPriorityQueueImpl(stringLengthComparator)
// 3
arrayListOf("one", "two", "three", "forty", "five", "six", "seven", "eight", "nine").forEach {
priorityQueue.enqueue(it)
}
// 4
while (!priorityQueue.isEmpty) {
println(priorityQueue.dequeue())
}
}
---Example of min priority queue---
forty
three
eight
seven
nine
five
two
one
six
Challenges
Challenge 1: Constructing ArrayList priority queues
You learned to use a heap to construct a priority queue by implementing the Queue interface. Now, construct a priority queue using an ArrayList:
interface Queue<T> {
fun enqueue(element: T): Boolean
fun dequeue(): T?
val count: Int
get
val isEmpty: Boolean
get() = count == 0
fun peek(): T?
}
Solution 1
Recall that a priority queue dequeues element in priority order. It could either be a min or max priority queue. To make an array-based priority queue, you need to implement the Queue interface. Instead of using a heap, you can use an array list.
// 1
abstract class AbstractPriorityQueueArrayList<T> : Queue<T> {
// 2
protected val elements = ArrayList<T>()
// 3
abstract fun sort()
// more to come ...
}
override val count: Int
get() = elements.size
override fun peek() = elements.firstOrNull()
override fun dequeue() =
if (isEmpty) null else elements.removeAt(0)
override fun enqueue(element: T): Boolean {
// 1
elements.add(element)
// 2
sort()
// 3
return true
}
override fun toString() = elements.toString()
class ComparablePriorityQueueArrayList<T : Comparable<T>> : AbstractPriorityQueueArrayList<T>() {
override fun sort() {
Collections.sort(elements)
}
}
class ComparatorPriorityQueueArrayList<T>(
private val comparator: Comparator<T>
) : AbstractPriorityQueueArrayList<T>() {
override fun sort() {
Collections.sort(elements, comparator)
}
}
class CustomPriorityQueueArrayList<T : Comparable<T>> : AbstractPriorityQueueArrayList<T>() {
override fun sort() {
var index = count - 2
while (index >= 0 &&
elements[index + 1].compareTo(elements[index]) > 0) {
swap(index, index + 1)
index--;
}
}
private fun swap(i: Int, j: Int) {
val tmp = elements[i]
elements[i] = elements[j]
elements[j] = tmp
}
}
"max priority array list based queue" example {
val priorityQueue = CustomPriorityQueueArrayList<Int>()
arrayListOf(1, 12, 3, 4, 1, 6, 8, 7).forEach {
priorityQueue.enqueue(it)
}
priorityQueue.enqueue(5)
priorityQueue.enqueue(0)
priorityQueue.enqueue(10)
while (!priorityQueue.isEmpty) {
println(priorityQueue.dequeue())
}
}
Challenge 2: Sorting
Your favorite concert was sold out. Fortunately, there’s a waitlist for people who still want to go. However, the ticket sales will first prioritize someone with a military background, followed by seniority.
data class Person(
val name: String,
val age: Int,
val isMilitary: Boolean)
Solution 2
Given a list of people on the waitlist, you would like to prioritize the people in the following order:
object MilitaryPersonComparator : Comparator<Person> {
override fun compare(o1: Person, o2: Person): Int {
if (o1.isMilitary && !o2.isMilitary) {
return 1
} else if (!o1.isMilitary && o2.isMilitary) {
return -1
} else if (o1.isMilitary && o2.isMilitary) {
return o1.age.compareTo(o2.age)
}
return 0
}
}
"concert line" example {
val p1 = Person("Josh", 21, true)
val p2 = Person("Jake", 22, true)
val p3 = Person("Clay", 28, false)
val p4 = Person("Cindy", 28, false)
val p5 = Person("Sabrina", 30, false)
val priorityQueue = ComparatorPriorityQueueImpl(MilitaryPersonComparator)
arrayListOf(p1, p2, p3, p4, p5).forEach {
priorityQueue.enqueue(it)
}
while (!priorityQueue.isEmpty) {
println(priorityQueue.dequeue())
}
}
---Example of concert line---
Jake
Josh
Cindy
Clay
Sabrina
Key points
- A priority queue is often used to find the element in priority order.
- The
AbstractPriorityQueue<T>implementation creates a layer of abstraction by focusing on key operations of aqueueand leaving out additional functionality provided by the heap data structure. - This makes the priority queue’s intent clear and concise. Its only job is to enqueue and dequeue elements, nothing else.
- The
AbstractPriorityQueue<T>implementation is another good example of Composition over (implementation) inheritance.