#StackBounty: #heap #kotlin Max-Heap Implementation in Kotlin

Bounty: 50

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 " }
    }
}
```


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.