1
\$\begingroup\$
open class Heap<T>: Iterable<Heap.Data<T>> {

    data class Data<T>(val item: T, var priority: Int) {
        operator fun compareTo(other:Data<T>): Int {
            return priority - other.priority
        }
    }


    protected var positions = mutableMapOf<T, Int>()
    protected var data: Array<Data<T>?>
    protected var heap_size:Int = 0

    override fun iterator(): Iterator<Heap.Data<T>> {
        return object : Iterator<Heap.Data<T>> {

            var index = 0
            override fun hasNext() = index < heap_size
            override fun next() = data[index++]!!
        }
    }

    constructor() {
        data = arrayOfNulls(1)
    }

    private fun swap(a:Int, b:Int) {
        val tmp = data[a]
        data[a] = data[b]
        data[b] = tmp

        positions[data[a]!!.item] = a
        positions[data[b]!!.item] = b

    }

    private fun left(root: Int) = (2  * root) + 1
    private fun right(root: Int) = (2 * root) + 2
    private fun parent(root: Int) = (root - 1) / 2

    fun insert(item: T, priority: Int) {
        insert(Data(item, priority))
    }



    protected fun insert(item: Data<T>) {
        if (heap_size == data.size)
            data = resize_arr(data.size * 2)

        var index = heap_size
        change_val(index, item)
        heap_size++
    }

    protected fun change_val(root: Int, new_val: Data<T>) {
        data[root] = new_val
        var index = root
        if (index != 0) {
            while (index != 0 && data[parent(index)]!! > data[index]!!) {
                swap(parent(index), index)
                index = parent(index)
            }
        } else
            positions[new_val.item] = root
    }


    fun pop(): Data<T>? {
        if (heap_size == 1)
            return data[--heap_size]!!

        if (heap_size == data.size / 4) {
            val new_size = if (data.size / 2 == 0) 2 else data.size / 2
            data = resize_arr(new_size)
        }

        val root = data[0]
        data[0] = data[heap_size - 1]
        heap_size--
        heapify(0)
        return root

    }

    private fun resize_arr(new_size: Int): Array<Data<T>?> {
        val new_arr = arrayOfNulls<Data<T>>(new_size)
        var index = 0
        while (index < heap_size) {
            new_arr[index] = data[index]
            index++
        }
        return new_arr
    }


    protected fun heapify(root: Int) {
        var left:Int
        var right:Int
        var min = root
        var _root = root
        while (true) {
            left = left(_root)
            right = right(_root)
            if (left < heap_size && data[left]!! < data[_root]!!)
                min = left
            if (right < heap_size && data[right]!! < data[min]!!)
                min = right
            if (min != _root) {
                swap(min, _root)
                _root = min
                min = _root
                continue
            }
            break
        }
    }

    fun change_priority(item: T, new_priority: Int) {
        val tmp = data[positions[item]!!]!!
        tmp.priority = new_priority
        data[positions[item]!!] = data[heap_size - 1]
        data[heap_size - 1] = null
        heap_size--
        heapify(positions[item]!!)
        insert(tmp)
    }
}

fun main(args:Array<String>) {
    val min_heap = Heap<String>()
    min_heap.insert("A", 5)
    min_heap.insert("B", 6)
    min_heap.insert("C", 7)
    min_heap.change_priority("A", 8)
    min_heap.change_priority("C", 1)
    min_heap.insert("D", 0)
    println(min_heap.pop())
    println(min_heap.pop())
    println(min_heap.pop())
    println(min_heap.pop())
}

output is:

Data(item=D, priority=0)
Data(item=C, priority=1)
Data(item=B, priority=6)
Data(item=A, priority=8)

Am I doing this right? is this implementation bad? any helpful tips and tricks for this newbie?

I wanted to implement a PriorityQueue that you can change values with.

and this is my attempt at it. any feedback would be great

\$\endgroup\$

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.