Priority Queue Implementation in Kotlin

1. Introduction

In this tutorial, we will learn how to implement a simple Priority Queue data structure using Kotlin programming language.

A Priority Queue is a specialized data structure that operates similarly to a regular Queue or Stack, but each element has a priority associated with it. Elements are added based on order of priority, and not just the order they're added. The dequeue operation removes the element with the highest priority. Common operations with a priority queue include enqueue, dequeue, and peek.

2. Implementation Steps

1. Define a class named PriorityQueue.

2. Initialize an empty list to store the elements and their priorities.

3. Implement the enqueue method to add elements to the priority queue with a given priority.

4. Implement the dequeue method to remove the element with the highest priority.

5. Implement the peek method to view the highest priority element without removing it.

6. Implement an isEmpty method to check if the priority queue is empty.

3. Implementation in Kotlin Programming

data class PQElement<T>(val data: T, val priority: Int)
class PriorityQueue<T> {
    private val elements: MutableList<PQElement<T>> = mutableListOf()
    
    // 3. Implement the `enqueue` method
    fun enqueue(item: T, priority: Int) {
        val pqElement = PQElement(item, priority)
        elements.add(pqElement)
        elements.sortByDescending { it.priority }
    }
    
    // 4. Implement the `dequeue` method
    fun dequeue(): T? {
        if (isEmpty()) {
            return null
        }
        return elements.removeAt(0).data
    }
    
    // 5. Implement the `peek` method
    fun peek(): T? {
        return elements.firstOrNull()?.data
    }
    
    // 6. Implement the `isEmpty` method
    fun isEmpty() = elements.isEmpty()
}

// Client code to demonstrate the priority queue functionality
val pq = PriorityQueue<String>()
pq.enqueue("Task 1", 2)
pq.enqueue("Task 2", 1)
pq.enqueue("Task 3", 3)
println(pq.peek())  // Expected Output: Task 3
println(pq.dequeue())   // Expected Output: Task 3
println(pq.peek())  // Expected Output: Task 1

Output:

Task 3
Task 3
Task 1

Explanation:

1. A PriorityQueue class is defined with type parameter T to make it generic.

2. The PQElement data class is defined to store the data and its associated priority.

3. Inside the PriorityQueue class, a mutable list named elements is initialized. This list holds the priority queue elements.

4. The enqueue method takes an item of type T and a priority, creates a PQElement and adds it to the elements list. It then sorts the list based on the priorities in descending order.

5. The dequeue method removes and returns the data of the first item (highest priority) from the elements list. If the priority queue is empty, it returns null.

6. The peek method returns the data of the first item (highest priority) from the elements list without removing it. If the priority queue is empty, it returns null.

7. The isEmpty method checks if the elements list is empty and returns a boolean value.