Max heap implementation in Kotlin

Question

I wrote this class a while ago to learn Kotlin and heaps, so any tips (on either my code style or my heap algorithm) would be appreciated!

class MaxHeap<T : Comparable<T>>() {
    private val items: MutableList<T?> = mutableListOf()
    var size: Int = 0
        private set

    fun push(item: T) {
        set(size++, item)
        siftUp(size - 1)
    }

    fun peek() = get(0)

    fun pop(): T? {
        // If there are no items in the heap, null is returned
        if (size == 0) {
            return null
        }

        // Get the max item, replace it with the last item in the heap,
        // then sift it down until the heap property is restored
        val max = peek()
        set(0, get(--size))
        items.removeAt(size) // Remove original reference to the last item
        siftDown(0)
        return max
    }

    private fun siftUp(i: Int) {
        assert(i >= 0 && i < size)

        // The root node has no parent, so we cannot sift up any more
        if (i == 0) {
            return
        }

        // If the current item is larger than the parent, swap them and
        // then repeat on the item, which is now in the parent position
        val iParent = parentIndex(i)
        if (get(i)!! > get(iParent)!!) {
            swap(i, iParent)
            siftUp(iParent)
        }
    }

    private fun siftDown(i: Int) {
        assert(i >= 0 && i < size)

        // Cannot sift down leaf nodes
        if (i >= size / 2) {
            return
        }

        // Find the larger child value.
        // Left child is guaranteed to exist because this is not a leaf node,
        // and because we add items to the heap by appending them to the end,
        // the left mode must be filled before the right node.
        val iLeft = leftChildIndex(i)
        val iRight = rightChildIndex(i)
        var iLargerChild = iLeft
        if (iRight < size && get(iLeft)!! < get(iRight)!!) {
            iLargerChild = iRight
        }

        // If this item is less than the larger child, sift it down
        if (get(i)!! < get(iLargerChild)!!) {
            swap(i, iLargerChild)
            siftDown(iLargerChild)
        }
    }

    private fun set(i: Int, value: T?) {
        if (i < items.size) {
            items[i] = value
        } else {
            items.add(value)
        }
    }

    private fun get(i: Int): T? {
        if (i < items.size) {
            return items[i]
        } else {
            return null
        }
    }

    private fun swap(i: Int, j: Int) {
        val temp = items[i]
        items[i] = items[j]
        items[j] = temp
    }

    private fun parentIndex(i: Int) = (i - 1) / 2
    private fun leftChildIndex(i: Int) = i * 2 + 1
    private fun rightChildIndex(i: Int) = i * 2 + 2
}

Answer 1

1. private val items: MutableList<T?> = mutableListOf() can be written more succinctly as private val items = mutableListOf<T?>() (the type is inferred and then no longer repeated (mostly) in an explicit type definition and the factory method call).

2. size can be backed by items.size:

   val size: Int
       get() = items.size
   
   fun push(item: T) {
       set(size + 1, item)
       siftUp(size - 1)
   }
   
   ...
   
   fun pop(): T? {
       ...
       set(0, get(size - 1))
       items.removeAt(items.lastIndex) // Remove original reference to the last item
       ...
   }
   

3. siftDown throws an AssertionError assertion when size == 0.

4. push and pop have different meanings in the Java Collections Framework associated with using a java.util.Deque as a stack. You might instead use the same verbs as java.util.PriorityQueue (namely add and remove) which can be used as a max heap:

   fun <T : Comparable<T>> maxHeap() = PriorityQueue<T>(Comparator.reverseOrder<T>())
   

Answer 2

This looks nice, though I don't actually know kotlin.

One suggestion I'd make is that when you have multiple relational conditions in a statement like this:

assert(i >= 0 && i < size)

It's slightly more readable if you arrange the terms in increasing order of their values, like this:

assert(0 <= i && i < size)

Answer 3

I'd introduce variables instead of comments. For example:

// If this item is less than the larger child, sift it down
    if (get(i)!! < get(iLargerChild)!!) {

can be rewritten as

var lessThanLargerChild : Boolean = get(i)!! < get(iLargerChild)!!
if (lessThanLargerChild) {

I'm not sure if this is correct Kotlin expression, I don't know the language but I hope you catched the idea.