Dynamic Priority Heap - Kotlin

Question

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.

Answer 1

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.