kotlin-priority-queue-feature-image

Kotlin Priority Queue tutorial with examples

In this tutorial, I will introduces Kotlin Priority Queue and examples that shows you how to work with it.

Related Posts:
Kotlin Queue tutorial with examples
Kotlin Comparator & Sort List of objects example
Kotlin – Compare Objects & Sort List with Comparable Example


Overview

A Priority Queue is a special type of Queue in that all the elements are ordered by natural ordering or by a custom Comparator provided at the time of creation.

The front of the Priority Queue contains the least element according to the ordering, and the rear contains the greatest element.

kotlin-priority-queue-data-structure

  • Remove an element from the Priority Queue => Dequeue the least element.
  • Peek an element from the Priority Queue => Get the least element.

The PriorityQueue class is part of Collections framework and implements the Queue interface. This is class hierarchy:

kotlin-priority-queue-class-hierarchy

Create Priority Queue in Kotlin

We’re gonna create several Priority Queues and add some elements to them.
Then we remove one by one item from the Queues and see how the least element is removed first followed by the next least element and so on.

– Priority Queue of Int items:

package com.bezkoder.kotlin.priorityqueue

import java.util.PriorityQueue

fun main(args: Array<String>) {
  val nums: PriorityQueue<Int> = PriorityQueue<Int>()

  // Add items (enqueue)
  nums.add(800)
  nums.add(50)
  nums.add(200)
  nums.add(550)

  println("peek: " + nums.peek())
  
  // Remove items (dequeue)
  while (!nums.isEmpty()) {
    println(nums.remove())
  }
}

Output:

peek: 50
50
200
550
800

– Priority Queue of String items:

package com.bezkoder.kotlin.priorityqueue

import java.util.PriorityQueue

fun main(args: Array<String>) {
  val names: PriorityQueue<String> = PriorityQueue<String>()

  // Add items (enqueue)
  names.add("Jack")
  names.add("Alex")
  names.add("Katherin")
  names.add("Watson")
  names.add("Jason")
  names.add("Hector")
  
  println("peek: " + names.peek())

  // Remove items (dequeue)
  while (!names.isEmpty()) {
    println(names.remove())
  }
}

Output:

peek: Alex
Alex
Hector
Jack
Jason
Katherin
Watson

Kotlin Priority Queue with Comparator

How about creating a Priority Queue of String items in which the String with the smallest length is processed first.
We need a Comparator that compares two Strings by their length.

To create Comparator, we use compareBy function.

package com.bezkoder.kotlin.priorityqueue

import java.util.PriorityQueue

fun main(args: Array<String>) {
  val compareByLength: Comparator<String> = compareBy { it.length }

  val namesQueueByLength = PriorityQueue<String>(compareByLength)

  namesQueueByLength.add("Jack")
  namesQueueByLength.add("Alex")
  namesQueueByLength.add("Katherin")
  namesQueueByLength.add("Watsons")
  namesQueueByLength.add("Jason")
  namesQueueByLength.add("Hector")

  while (!namesQueueByLength.isEmpty()) {
    println(namesQueueByLength.remove())
  }
}

Output:

Jack
Alex
Jason
Hector
Watsons
Katherin

Kotlin Priority Queue of custom objects

Assume that we have a Customer class:

Customer.kt

package com.bezkoder.kotlin.priorityqueue

data class Customer(val name: String, val age: Int) {
}

Now look at the case that we need to create a Priority Queue of Customer objects and order them by age, then by name. How to do this?

Using Comparator

We’re gonna define a custom Comparator. One way is to create CustomerComparator class with companion object like following code:

CustomerComparator.kt

package com.bezkoder.kotlin.priorityqueue

class CustomerComparator {

  companion object : Comparator<Customer> {

    override fun compare(a: Customer, b: Customer): Int = when {
      a.age != b.age -> a.age - b.age
      else -> a.name.compareTo(b.name)
    }
  }
}

Now we only need to declare PriorityQueue<Customer> with CustomerComparator.

app.kt

package com.bezkoder.kotlin.priorityqueue

import java.util.PriorityQueue

fun main(args: Array<String>) {
  val customers = PriorityQueue<Customer>(CustomerComparator)
  
  customers.add(Customer("Jack", 26))
  customers.add(Customer("Alex", 35))
  customers.add(Customer("Katherin", 21))
  customers.add(Customer("Watsons", 18))
  customers.add(Customer("Jason", 32))
  customers.add(Customer("Hector", 18))
  
  while (!customers.isEmpty()) {
    println(customers.remove())
  }
}

Output:

Customer(name=Hector, age=18)
Customer(name=Watsons, age=18)
Customer(name=Katherin, age=21)
Customer(name=Jack, age=26)
Customer(name=Jason, age=32)
Customer(name=Alex, age=35)

Using Comparable

Another way is to implements Comparable interface and override compareTo() method.

So we rewrite our Customer class like this.

Customer.kt

package com.bezkoder.kotlin.priorityqueue

data class Customer(val name: String, val age: Int) : Comparable<Customer> {

  override fun compareTo(other: Customer) = when {
    age != other.age -> age - other.age
    else -> name.compareTo(other.name)
  }
}

Now we don’t need any Comparator when creating Priority Queue.

app.kt

package com.bezkoder.kotlin.priorityqueue

import java.util.PriorityQueue

fun main(args: Array<String>) {
  val customers = PriorityQueue<Customer>()

  customers.add(Customer("Jack", 26))
  customers.add(Customer("Alex", 35))
  customers.add(Customer("Katherin", 21))
  customers.add(Customer("Watsons", 18))
  customers.add(Customer("Jason", 32))
  customers.add(Customer("Hector", 18))

  while (!customers.isEmpty()) {
    println(customers.remove())
  }
}

Output:

Customer(name=Hector, age=18)
Customer(name=Watsons, age=18)
Customer(name=Katherin, age=21)
Customer(name=Jack, age=26)
Customer(name=Jason, age=32)
Customer(name=Alex, age=35)

Conclusion

Today we’ve known what is a Priority Queue, how to create and use a Kotlin Priority Queue with a Comparator, and way to create Priority Queue with custom objects.

You can also learn how to use Comparator or Comparable to sort List of objects in the articles:
Kotlin Comparator & Sort List of objects example
Kotlin – Compare Objects & Sort List with Comparable Example

Happy Learning! See you again.

Further Reading

Leave a Reply

Your email address will not be published. Required fields are marked *