加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 编程开发 > Java > 正文

Min Heap in Kotlin

发布时间:2020-12-15 05:28:58 所属栏目:Java 来源:网络整理
导读: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 } priv
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()
            }
        }
    }

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读