Chapters

Hide chapters

Data Structures & Algorithms in Kotlin

First Edition · Android 10 · Kotlin 1.3 · IDEA

Before You Begin

Section 0: 3 chapters
Show chapters Hide chapters

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 scrambled 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 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.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now