## Data Structures & Algorithms in Kotlin

Second Edition · Android 11 · Kotlin 1.5 · IntelliJ IDEA Community Edition 2021.1

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

Section 1: 2 chapters

#### Section II: Elementary Data Structures

Section 2: 3 chapters

#### Section IV: Sorting Algorithms

Section 4: 5 chapters

# 13. Priority Queues Written by Irina Galata

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: Any> {

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: Any> : 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: Any>(
private val comparator: Comparator<T>
) : AbstractPriorityQueue<T>() {

override val heap = ComparatorHeapImpl(comparator)
}
``````
``````"min priority queue" example {
// 1
val stringLengthComparator = Comparator<String> { o1, o2 ->
val length1 = o1?.length ?: -1
val length2 = o2?.length ?: -1
length1 - length2
}
// 2
val priorityQueue = ComparatorPriorityQueueImpl(stringLengthComparator)
// 3
arrayListOf("one", "two", "three", "four", "five", "six", "seven", "eight", "nine").forEach {
priorityQueue.enqueue(it)
}
// 4
while (!priorityQueue.isEmpty) {
println(priorityQueue.dequeue())
}
}
``````
``````---Example of min priority queue---
three
eight
seven
nine
four
five
one
two
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: Any> {

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 elements 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: Any> : 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: Any>(
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.