There is an updated edition of this book available! View Latest Edition

## Data Structures & Algorithms in Kotlin

#### Before You Begin

Section 0: 3 chapters

#### Section I: Introduction to Data Structures & Algorithms

Section 1: 2 chapters

#### Section II: Elementary Data Structures

Section 2: 3 chapters

#### Section III: Trees

Section 3: 8 chapters

#### Section IV: Sorting Algorithms

Section 4: 5 chapters

#### Section V: Graphs

Section 5: 6 chapters

# 13 Priority Queues Written by Irina Galata, Kelvin Lau and Vincent Ngo

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
// 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 a queue and 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.
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.