DS Priority Queue Operations and Usage

Subsection 9.3.1 Priority Queue Operations

The basic operations we will implement for our priority queue are as follows:

PriorityQueue() creates a new empty binary heap.
🔗

🔗
PriorityQueue(list) builds a new heap from a list of items.
🔗

🔗
insert(k) adds a new item to the priority queue.
🔗

🔗
peek() returns the item with the minimum key value, leaving the item in the priority queue.
🔗

🔗
delete() returns the item with the minimum key value, removing the item from the priority queue.
🔗

🔗
isEmpty() returns True if the heap is empty, False otherwise.
🔗

🔗
size() returns the number of items in the priority queue.
🔗

🔗

We have specified two different constructors in the operations list above. The first one is the usual one, which creates an empty priority queue. The second specifies that we can supply an initial list of items. We’ve chosen to highlight this constructor here because there’s an interesting implementation for it when we look at the binary heap.

🔗

Here is an interface in Kotlin representing the above. One limitation of Kotlin is that we cannot specify a constructor in an interface. Therefore, we will document it with a comment.

🔗

Listing 9.3.1. Interface for Priority Queue ADT

🔗

interface PriorityQueueADT<E: Comparable<E>> {
    // Two constructors should be implemented:
    // PriorityQueueADT()
    //     creates an empty priority queue
    //
    // PriorityQueueADT(List<E> initialList)
    //     creates a priority queue initialized with items
    //     present in initialList

    // Other methods:

    // Adds the element to the priority queue.
    fun insert(element: E)

    // Returns item with minimum value, leaving item in the priority queue.
    // Returns null if empty.
    fun peek(): E?

    // Deletes the item with minimum value, removing it from the priority queue.
    // Returns the value deleted, or null if the priority queue was empty.
    fun delete(): E?

    // Returns true if priority queue is empty, false otherwise
    fun isEmpty(): Boolean

    // Returns the number of items in the heap.
    fun size(): Int
}

🔗

Subsection 9.3.2 Priority Queue Usage: Single Values

Listing 9.3.2 demonstrates the use of a priority queue, in storing integers, using the implementation that we will build in the next section.

🔗

Listing 9.3.2. Sample usage of priority queue, with integers.

🔗

interface PriorityQueueADT<E: Comparable<E>> {
    // Two constructors should be implemented:
    // PriorityQueueADT()
    //     creates an empty priority queue
    //
    // PriorityQueueADT(List<E> initialList)
    //     creates a priority queue initialized with items
    //     present in initialList

// Other methods:

// Adds the element to the priority queue.
    fun insert(element: E)

// Returns item with minimum value, leaving item in the priority queue.
    // Returns null if empty.
    fun peek(): E?

// Deletes the item with minimum value, removing it from the priority queue.
    // Returns the value deleted, or null if the priority queue was empty.
    fun delete(): E?

// Returns true if priority queue is empty, false otherwise
    fun isEmpty(): Boolean

// Returns the number of items in the heap.
    fun size(): Int
}
class BinaryHeapPriorityQueue<E: Comparable<E>>() : PriorityQueueADT<E> {

var heap = mutableListOf<E>()

constructor(nonHeap: List<E>): this() {
        heapify(nonHeap)
    }

private fun heapify(nonHeap: List<E>) {
        if (nonHeap.count() > 0) {
            heap = nonHeap.toMutableList()  // copies list

var currIndex = heap.count() / 2 - 1
            while (currIndex >= 0) {
                percolateDown(currIndex)
                currIndex -= 1
            }
        }
    }

private fun swapItemsAt(index1: Int, index2: Int) {
        val temporary = heap[index1]
        heap[index1] = heap[index2]
        heap[index2] = temporary
    }

private fun percolateUp(index: Int) {
        var index = index
        while (index > 0) {
            val parentIndex = (index - 1) / 2
            if (heap[index] < heap[parentIndex]) {
                swapItemsAt(index, parentIndex)
            }
            index = parentIndex
        }
    }

override fun insert(element: E) {
        heap.add(element)
        percolateUp(heap.count() - 1)
    }

private fun percolateDown(index: Int) {
        var index = index
        while (2 * index + 1 < heap.count()) {
            val smallerChild = getSmallerChild(index)
            if (heap[index] > heap[smallerChild]) {
                swapItemsAt(index, smallerChild)
            } else {
                break
            }
            index = smallerChild
        }
    }

private fun getSmallerChild(index: Int): Int {
        if (2 * index + 2 > heap.count() - 1) {
            return 2 * index + 1
        }
        if (heap[2 * index + 1] < heap[2 * index + 2]) {
            return 2 * index + 1
        }
        return 2 * index + 2
    }

override fun delete(): E? {
        if (heap.count() == 0) {
            return null
        }

val result = heap[0]
        swapItemsAt(0, heap.count() - 1)
        heap.removeLast()
        percolateDown(0)
        return result
    }

override fun peek(): E? {
        if (heap.count() == 0) {
            return null
        } else {
            return heap[0]
        }
    }

override fun isEmpty(): Boolean {
        return heap.count()==0
    }

override fun size(): Int {
        return heap.count()
    }

override fun toString(): String {
        return heap.toString()
    }

}
^^^^
fun main() {
    val myPq = BinaryHeapPriorityQueue<Int>()
    myPq.insert(5)
    myPq.insert(7)
    myPq.insert(3)
    myPq.insert(11)
    println("Min value: " + myPq.peek())

println("Deleting items: ")
    println(myPq.delete())
    println(myPq.delete())
    println(myPq.delete())
    println(myPq.delete())
}

Here is its output:

🔗

Min value: 3
Deleting items: 
3
5
7
11

Notice that no matter what order we add items to the heap, the smallest is removed each time.

🔗

Subsection 9.3.3 Priority Queue Usage: Priority Values And Data

What if we want to use our priority queue where we want to store both a priority value, and data that goes with it? For example, suppose that we are at a zoo, and we are using a priority queue to track which animal is most important for us to see next. We can use an integer to represent the priority (lower is better), but we also need to also store the animal. We can store both of these in the priority queue if we store objects from a data class. Here is an initial attempt at that data class:

🔗

data class Animal(val priority: Int, val name: String)

The above definition of Animal is a good starting point, but Kotlin needs to be able to do ordering comparisons (i.e., less-than and greater-than comparisons) between Animal objects in order to determine which one has higher priority. Ordering comparisons don’t work out-of-the-box for arbitrary objects. In order to make them work on this data class, we need to help Kotlin understand what it means for one animal to be "smaller" than another.

🔗

In order to give Kotlin information on relative ordering of Animal objects, we indicate that the Animal class implements the Comparable interface, which enables Kotlin to perform less-than and greater-than operations. Here then, is our next step at defining the Animal class:

🔗

data class Animal(val priority: Int, val name: String): Comparable<Animal>

The Comparable interface requires that when we create a class implementing it, we need to override one method, named compareTo, which provides information on how to compare two Comparable objects. Whenever a comparison like x < y or x > y is made, Kotlin translates that into a call that looks like x.compareTo(y). Here is how the results are understood:

If x.compareTo(y) returns a negative value, this means that x is less than y.
🔗

🔗
If x.compareTo(y) returns a positive value, this means that x is greater than y.
🔗

🔗
If x.compareTo(y) returns zero, this means that x is equal to y.
🔗

🔗

Therefore, we create a method named compareTo, and obtain its value by subtracting the second value from the first. This results in compareTo returning negative and positive numbers as specified. The code below shows the final version of our data class, and how to use it with a priority queue.

🔗

Listing 9.3.3. Sample usage of priority queue, with a data class.