1
\$\begingroup\$

I am concerned about a few things about my heap implementation. This is in Kotlin.

For starters-

  • When and when not to use expressions?
  • The use of also to swap numbers

Other suggestions about the algorithm and the code are welcome.

class BinaryHeap : Iterable<Int> {

    private val array = mutableListOf(0)
    var heapSize = 0

    override fun iterator(): Iterator<Int> = array.iterator()

    private fun parent(i: Int) = i.shr(1)

    private fun left(i: Int) = i.shl(1)

    private fun right(i: Int) = i.shl(1).plus(1)

    private fun maxHeapify(i: Int) {

        var largest: Int
        val left = left(i)
        val right = right(i)

        largest = if (left <= heapSize && array[i] > array[left]) i
        else if (left <= heapSize) left
        else i

        if (right <= heapSize && array[largest] < array[right])
            largest = right

        if (largest != i) {
            swap(largest, i)
            maxHeapify(largest)
        }

    }

    val max = if (heapSize != 0) array[1] else -1

    fun extractMax(): Int {
        return if (heapSize < 1)
            -1
        else {
            val max = array[1]
            array[1] = array[heapSize]
            heapSize--
            maxHeapify(1)
            max
        }
    }

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

    fun insert(i: Int) {
        if (array.size > heapSize + 1)
            array[++heapSize] = i
        else {
            array.add(i)
            heapSize++
        }
        var badNode = heapSize
        var parentBadNode = parent(badNode)
        while (parentBadNode != 0 && array[parentBadNode] < array[badNode]) {
            swap(parentBadNode, badNode)
            badNode = parentBadNode.also { parentBadNode = parent(parentBadNode) }
        }
    }

    fun insert(i: Iterable<Int>) {
        i.forEach {
            insert(it)
        }
    }

    override fun toString(): String {
        return array.joinToString { "$it " }
    }
}
```
\$\endgroup\$
  • 2
    \$\begingroup\$ I'm confused by "The round function has an odd behavior it rounds down x.5 to x". (1) There isn't any round in the code. (2) There's nothing odd about that. The only thing which might be considered odd is not having learnt from the previous 50 years of experience of library development that round methods should take a parameter indicating what to do with x.5 (up, down, to zero, away from zero, or to even). \$\endgroup\$ – Peter Taylor Jul 3 at 15:35
  • \$\begingroup\$ Yea my bad. I should have mentioned that the behavior of round was just a general inquiry. About the parameter, I don't think one exists in Java or Kotlin. \$\endgroup\$ – Omkar Sabade Jul 3 at 16:23

Your Answer

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

Browse other questions tagged or ask your own question.