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>())
   

• Andrew Sun: Hmm, under what conditions can i == size be true?
• mfulton26: @AndrewSun I suggest creating some unit tests. :-) That is how I caught it although after inspecting the code closer my suggested fix was probably not the best solution. As such, I've updated my #3 to simply state the problem. The best fix might be to only call siftDown if size > 1. An alternative would be to move the assertion to after the i >= size / 2 check. I'm sure there are other ways to fix it as well.
• Andrew Sun: Ahh, I see the problem, thanks. I actually did have some tests (including removing all items from the heap), I think what happened is that assertions weren't even enabled :-p I agree that not calling siftDown when the heap is empty would be the best solution, so the assertion would still work in all other cases.
• mfulton26: @AndrewSun Awesome. In the future, you might even include your tests in the code review. I personally find no better documentation for main code than test code.

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.