trjhtr

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