Min Heap in Kotlin

class MinHeap constructor(maxSize_: Int) {
        var size = 0
        var maxSize = maxSize_
        var heapArray: Array<Int>? = null

        companion object {
            const val FRONT = 1
        }

        init {
            size = 0
            heapArray = Array(maxSize,{0})
            heapArray!![0] = Int.MIN_VALUE
        }

        private fun parent(position: Int): Int {
            return position / 2
        }

        private fun leftChild(position: Int): Int {
            return (position * 2)
        }

        private fun rightChild(position: Int): Int {
            return (position * 2) + 1
        }

        private fun isLeaf(position: Int): Boolean {
            if (position >= (size / 2) && position <= size) {
                return true
            }
            return false
        }

        private fun swap(pos1: Int, pos2: Int) {
            val temp = heapArray!![pos1]
            heapArray!![pos1] = heapArray!![pos2]
            heapArray!![pos2] = temp
        }

        private fun minHeapify(pos: Int) {
            if (!isLeaf(pos)) {
                if (heapArray!![pos] > leftChild(pos) || heapArray!![pos] > rightChild(pos)) {
                    if (heapArray!![leftChild(pos)] < heapArray!![rightChild(pos)]) {
                        swap(pos, leftChild(pos))
                        minHeapify(leftChild(pos))
                    } else {
                        swap(pos, rightChild(pos))
                        minHeapify(rightChild(pos))
                    }
                }
            }
        }

        fun insert(element: Int) {
            if (size >= maxSize) {
                return
            }
            heapArray!![++size] = element
            var current = size
            while (heapArray!![current] < heapArray!![parent(current)]) {
                swap(current, parent(current))
                current = parent(current)
            }
        }

        fun minHeap(){
            for (i in (size/2)..1){
                minHeapify(i)
            }
        }

        /**
         * remove and return the minimum element from the heap
         * */
        fun remove():Int{
            val poped = heapArray!![FRONT]
            heapArray!![FRONT] = heapArray!![size--]
            minHeapify(FRONT)
            return poped
        }

        fun print() {
            for (i in 1..size / 2) {
                System.out.print(" PARENT: " + heapArray!![i]
                        + ", LEFT CHILD : " + heapArray!![2 * i]
                        + ", RIGHT CHILD :" + heapArray!![2 * i + 1])
                println()
            }
        }
    }
原文地址:https://www.cnblogs.com/johnnyzhao/p/11296939.html