Understanding Priority Queue in Kotlin

When it comes to solving problems that require efficient data management, the Priority Queue is a data structure that often takes center stage. It’s a versatile tool for maintaining a dynamic collection of elements with relative priorities. In this blog post, we will delve into the world of Priority Queues in Kotlin, covering what they are, their types, practical examples, use cases, time complexities, and their advantages and disadvantages.

What is PriorityQueue?

This is a data structure that maintains a set of elements, each associated with a priority.

It’s like standing in line for a roller coaster: the ride operator lets people with VIP passes (higher priority) board before the others.

Priority Queues can be implemented using various data structures, such as binary heaps, and they are commonly used in algorithms like Dijkstra’s algorithm and A* search.

Types of PriorityQueue

Priority Queues come in several flavors:

1. Min Heap: In a min heap, the element with the lowest priority (minimum value) is served first.

Example to Sort Integer:

Example 1:
fun minPriority()
{
val minPriorityQueue = PriorityQueue<Int>()
minPriorityQueue.add(20)
minPriorityQueue.add(10)
minPriorityQueue.add(5)

println("Elements in the Min-Priority Queue.")

while(minPriorityQueue.isNotEmpty())
{
print("${minPriorityQueue.poll()} ") 
}
}

//output: 
Elements in the Min-Priority Queue.
5 10 20

Example to Sort Collection — List

fun sortCollectionUsingPriorityQueue()
{
    val unsortedList = listOf(5, 2, 9, 1, 5)
    val sortedList = PriorityQueue(unsortedList)

    println("Sorting Collection using Priority Queue:")
    while (sortedList.isNotEmpty()) {
        print("${sortedList.poll()} ")
    }
}

output:
Sorting Collection using Priority Queue:
1 2 5 5 9

In this example, we use a min-priority queue to ensure that the elements are retrieved in ascending order.

2. Max Heap In a max heap, the element with the highest priority (maximum value) is served first.

private fun maxPriorityQueue() {
    val maxPriorityQueue = PriorityQueue<Int> { o1, o2 -> o2 - o1 }

    maxPriorityQueue.add(3)
    maxPriorityQueue.add(1)
    maxPriorityQueue.add(2)

    println("Elements in the Max-Priority Queue:")
    while (maxPriorityQueue.isNotEmpty()) {
    print("${maxPriorityQueue.poll()} ")  
  }
}

//output: 
Elements in the Max-Priority Queue.
3 2 1

3. Using Comparator Sometime we need to prioritise elements based on custom criteria. In Kotlin, We can create a Priority Queue with a custom comparator to accommodate this.

    private fun comparatorPriorityQueue() {
        val comparatorPriorityQueue = PriorityQueue<Person>(PersonComparator())

        comparatorPriorityQueue.add(Person("Alex",20))
        comparatorPriorityQueue.add(Person("Bee",22))
        comparatorPriorityQueue.add(Person("Zoe",30))
        comparatorPriorityQueue.add(Person("Zoya",23))
        comparatorPriorityQueue.add(Person("Bee",30))


        println("Sorting of elements using Comparator in Priority Queue:")
        while (comparatorPriorityQueue.isNotEmpty()) {
            println(comparatorPriorityQueue.poll())
        }
    }

    // Person Class
    data class Person(val name:String, val age:Int)


    //Custom Comparator to sort the person according to his age and 
    // if ages appears same then sort using name
    class PersonComparator : Comparator<Person>
    {
        override fun compare(o1: Person, o2: Person): Int = when {
            o1.age !=o2.age -> o1.age - o2.age
            else -> o1.name.compareTo(o2.name)
        }

    }


//output
Sorting of elements using Comparator in Priority Queue::
Person(name=Alex, age=20)
Person(name=Bee, age=22)
Person(name=Zoya, age=23)
Person(name=Bee, age=30)
Person(name=Zoe, age=30)

4. Using Comparable Another way is to implement Comparable interface and override compareTo() method. Person class in inheriting comparable property compareTo(). Now we dont need any comparator while creating Priority Queue.

 data class Person(val name:String, val age:Int) : Comparable<Person>
    {
        override fun compareTo(other: Person): Int = when {
            age !=other.age -> age - other.age
            else -> name.compareTo(other.name)
        }
    }

 private fun comparablePriorityQueue() {
        val comparatorPriorityQueue = PriorityQueue<Person>()

        comparatorPriorityQueue.add(Person("Alex",20))
        comparatorPriorityQueue.add(Person("Bee",22))
        comparatorPriorityQueue.add(Person("Zoe",30))
        comparatorPriorityQueue.add(Person("Zoya",23))
        comparatorPriorityQueue.add(Person("Bee",30))


        println("Sorting of elements using Comparable in Priority Queue:")
        while (comparatorPriorityQueue.isNotEmpty()) {
            println(comparatorPriorityQueue.poll())
        }
    }

output:
Sorting of elements using Comparable in Priority Queue:
Person(name=Alex, age=20)
Person(name=Bee, age=22)
Person(name=Zoya, age=23)
Person(name=Bee, age=30)
Person(name=Zoe, age=30)

Time Complexity of Priority Queue

The time complexity of Priority Queue operations can vary depending on the implementation, but in general:

• Insertion (push): O(log n) time complexity, as inserting an element involves placing it in the next available position and then restoring the heap property, which takes logarithmic time.
• Removal (pop): O(log n) time complexity, where n is the number of elements in the heap. Removing the root and restoring the heap property requires logarithmic time.
• Finding the top element (peek): O(1) — The minimum (or maximum) element is always at the root, so accessing it is a constant-time operation.

Advantages and Disadvantage of Priority Queue

Advantages

1. Efficiently manages elements with different priorities.

2. Allows for constant-time access to the element with the highest priority.

3. Versatile data structure for a wide range of problems and algorithms.

Disadvantages

1. Priority Queues have higher overhead than simple arrays or linked lists.
2. Depending on the implementation, they may not be as memory-efficient as other data structures.
3. Customising the priority comparison logic can be complex in some cases.

Scenarios when we can apply Priority Queue

Priority Queues are versatile data structures, and they shine in various scenarios where you need to efficiently manage elements with different priorities. Here are some common use cases and corresponding LeetCode problems that demonstrate these scenarios:

Dijkstra’s Shortest Path Algorithm:

• Scenario: Finding the shortest path in a weighted graph.
• LeetCode Problem: LeetCode 743 — Network Delay Time

Prim’s Minimum Spanning Tree Algorithm:

• Scenario: Finding the minimum spanning tree of a weighted graph.
• LeetCode Problem: LeetCode 1584 — Min Cost to Connect All Points

A Search Algorithm*:

• Scenario: Finding the shortest path in a grid with obstacles.
• LeetCode Problem: LeetCode 937 — Reorder Data in Log Files

Merge K Sorted Lists:

• Scenario: Merging K sorted lists into a single sorted list.
• LeetCode Problem: LeetCode 23 — Merge k Sorted Lists

Top K Frequent Elements:

• Scenario: Finding the top K frequent elements in an array.
• LeetCode Problem: LeetCode 347 — Top K Frequent Elements

Sliding Window Problems:

• Scenario: Managing a sliding window of elements.
• LeetCode Problem: LeetCode 480 — Sliding Window Median

Task Scheduling:

• Scenario: Scheduling tasks to maximize CPU usage.
• LeetCode Problem: LeetCode 621 — Task Scheduler

Merge Intervals:

• Scenario: Merging overlapping intervals.
• LeetCode Problem: LeetCode 56 — Merge Intervals

Maximum Sliding Window:

• Scenario: Finding the maximum element in a sliding window of fixed size.
• LeetCode Problem: LeetCode 239 — Sliding Window Maximum

These problems showcase the utility of Priority Queues in various algorithms and real-world scenarios.

Conclusion

Priority Queues are indispensable for solving problems that require efficient prioritization and dynamic data management. Whether you need to find the shortest path in a graph, efficiently manage tasks, or tackle various other prioritization problems, a Priority Queue in Kotlin can be your go-to tool. By mastering Priority Queues, you’ll enhance your problem-solving capabilities and be well-equipped to tackle a broad range of challenges in computer science and software development.