6
\$\begingroup\$

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
}
\$\endgroup\$
4
\$\begingroup\$
  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>())
    
\$\endgroup\$
  • \$\begingroup\$ Hmm, under what conditions can i == size be true? \$\endgroup\$ – Andrew Sun Mar 15 '16 at 2:30
  • 1
    \$\begingroup\$ @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. \$\endgroup\$ – mfulton26 Mar 15 '16 at 13:11
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Andrew Sun Mar 15 '16 at 14:23
  • \$\begingroup\$ @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. \$\endgroup\$ – mfulton26 Mar 15 '16 at 15:57
5
\$\begingroup\$

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

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)
\$\endgroup\$
2
\$\begingroup\$

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.

\$\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.