0
\$\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.

This is my attempt at it. Any feedback would be great.

\$\endgroup\$

1 Answer 1

3
\$\begingroup\$

I am at a loss about the role of change values/change_val(),
lack of in-code documentation contributing - there is KDoc.
It may be due to not using the common names sift-up&sift-down.

insert(item, priority) might check whether item already is in positions.
This may be a good place to design and specify exceptions.

In pop(), resize after decreasing size.

In change_priority(), one could compare old and new priority and let the item stay in place, sift-up or sift-down accordingly.

change_val() and heapify() do avoidable assignments of "the moving" Data to indices where it doesn't stay.

You don't need continue in heapify():

            if (min == _root)
                break
            swap(min, _root)
            _root = min
            min = _root

But I think the loop termination indirect anyway:

    /** Set data and keep position */
    private fun put(item:Data<T>?, at:Int) {
        data[at] = item
        positions[item!!.item] = at
    }

    protected fun heapify(root: Int) {
        var left = left(root)
        val sinking = data[root]!!  // pick up
        var _root = root            // an index to bubble up to
        // two conditions to quit looping:
        while (left < heap_size) {  // 1: at leaf
            var min = left
            var minData = data[left]!!
            val right = right(_root)
            if (right < heap_size) {
                val rightData = data[right]!!
                if (rightData < minData) {
                    min = right
                    minData = rightData
                }
            }
            if (sinking <= minData)  // 2: sunk deep enough
                break
            put(minData, _root)  // bubble up
            _root = min
            left = left(_root)
        }
        if (root != _root)
            put(sinking, _root)  // put down
    }

Dynamic priority heap suggests removal as a useful extension.

\$\endgroup\$
1
  • \$\begingroup\$ thank you for the constructive input \$\endgroup\$ Commented Nov 18, 2023 at 18:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.