2
\$\begingroup\$

Below you can find a generic implementation and some unit tests of a minimum priority queue in Kotlin.

What could be improved in this implementation, so that it complies to best coding practices in Kotlin?

import java.util.*

class MinHeapPQ<Key> : Iterable<Key> {

    private var pq: Array<Key?>

    private var n = 0

    private var comparator: Comparator<Key>? = null

    constructor(initCapacity: Int) : this(initCapacity, null)

    constructor() : this(1)

    constructor(comparator: Comparator<Key>?) : this(1, comparator)

    constructor(initCapacity: Int, comparator: Comparator<Key>?) {
        this.comparator = comparator
        pq = arrayOfNulls<Any?>(initCapacity + 1) as Array<Key?>
    }

    constructor(keys: Array<Key>) : this(keys.size) {
        n = keys.size
        for (i in 0..n - 1) {
            pq[i + 1] = keys[i]
        }
        for (k in n / 2 downTo 1) {
            sink(k)
        }
        assert(isMinHeap())
    }

    fun isEmpty() = n == 0

    fun size() = n

    fun min(): Key {
        require(!isEmpty()) { "Priority queue underflow" }
        return pq[1]!!
    }

    fun insert(x: Key): MinHeapPQ<Key> {
        if (n == pq.size - 1) {
            resize(2 * pq.size)
        }
        pq[++n] = x
        swim(n)
        assert(isMinHeap())
        return this
    }

    fun delMin(): Key {
        require(!isEmpty()) { "Cannot retrieve minimum record. Priority queue is empty" }
        val min = pq[1]
        exch(1, n--)
        sink(1)
        pq[n + 1] = null
        assert(isMinHeap())
        return if (min != null) min else throw NullPointerException("'min' must not be null")
    }

    override fun iterator(): Iterator<Key> {
        return HeapIterator(comparator, size(), n, pq)
    }

    private fun swim(k: Int) {
        var myK = k
        while (myK > 1 && greater(myK / 2, myK)) {
            exch(myK, myK / 2)
            myK /= 2
        }
    }

    private fun sink(k: Int) {
        var myK = k
        while (2 * myK <= n) {
            var j = 2 * myK
            if (j < n && greater(j, j + 1)) j++
            if (!greater(myK, j)) return
            exch(myK, j)
            myK = j
        }
    }

    private fun greater(i: Int, j: Int): Boolean {
        return if (comparator == null) (pq[i] as Comparable<Key>) > pq[j]!!
        else comparator!!.compare(pq[i], pq[j]) > 0
    }

    private fun exch(i: Int, j: Int) {
        pq[i] = pq[j].also { pq[j] = pq[i] }
    }

    private fun isMinHeap(): Boolean = isMinHeap(1)

    private fun isMinHeap(k: Int): Boolean {
        if (k > n) return true
        val left = 2 * k
        val right = 2 * k + 1
        when {
            left <= n && greater(k, left) -> return false
            right <= n && greater(k, right) -> return false
            else -> {
                return isMinHeap(left) && isMinHeap(right)
            }
        }
    }

    private fun resize(capacity: Int) {
        assert(capacity > n)
        val temp = arrayOfNulls<Any>(capacity) as Array<Key?>
        for (i in 1..n) {
            temp[i] = pq[i]
        }
        pq = temp
    }

    class HeapIterator<out Key>(comparator: Comparator<Key>?, size: Int, n: Int, pq: Array<Key?>) : Iterator<Key> {

        private val copy: MinHeapPQ<Key> = if (comparator == null) MinHeapPQ<Key>(size) else MinHeapPQ<Key>(size, comparator)

        override fun hasNext(): Boolean {
            return !copy.isEmpty()
        }

        override fun next(): Key {
            require(hasNext()) {"Queue is empty"}
            return copy.delMin()
        }

        init {
            for (i in 1..n)
                copy.insert(pq[i]!!)
        }

    }

}

Here are some JUnit 4 tests:

import org.hamcrest.core.Is.`is`
import org.junit.Assert.assertThat
import org.junit.Test

class MinHeapPQTest {

    @Test
    fun delMin() {
        val pq = MinHeapPQ<Int>()
        pq.insert(5).insert(9).insert(3)
        assertThat(pq.min(), `is`(3))
        pq.insert(10)
        assertThat(pq.delMin(), `is`(3))
        assertThat(pq.size(), `is`(3))
        assertThat(pq.delMin(), `is`(5))
        assertThat(pq.delMin(), `is`(9))
        assertThat(pq.delMin(), `is`(10))
        assertThat(pq.isEmpty(), `is`(true))
        assertThat(pq.size(), `is`(0))
    }

    @Test(expected = IllegalArgumentException::class)
    fun delMin_underflow() {
        val pq = MinHeapPQ<Int>()
        pq.min()
    }

    @Test
    fun iterator() {
        val pq = MinHeapPQ<Int>(arrayOf(10, 8, 3, 9, 7, 5, 6, 2, 1, 4))
        val sorted = pq.iterator().asSequence().toList()
        for (i in 1..10) {
            assertThat(sorted[i - 1], `is`(i))
        }
    }

}

This implementation is a port of Robert Sedgewick's and Kevin Wayne's MinPQ implementation. See http://algs4.cs.princeton.edu/24pq

\$\endgroup\$
3
\$\begingroup\$

Until

for (i in 0..n - 1) {

can be replaced with

for (i in (0 until n))

Lift return from when

when {
    left <= n && greater(k, left) -> return false
    right <= n && greater(k, right) -> return false
    else -> {
        return isMinHeap(left) && isMinHeap(right)
    }
}

can be replaced with

return when {
    left <= n && greater(k, left) -> false
    right <= n && greater(k, right) -> false
    else -> isMinHeap(left) && isMinHeap(right)
}
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.