Min Heap in Kotlin

╰半橙微兮° 2023-06-01 12:54 23阅读 0赞

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