/*
 * Heap.kt
 * 
 * This is Dave Musicant's Heap.kt from Fall 2024,
 * which was ported by Dave from the Heap code at
 * https://www.programiz.com/dsa/heap-data-structure.
 * 
 * Modified lightly by Tanya Amert for Spring 2025.
 * 
 * Illustrates an implementation of a Heap.
 */

// Heap class: implementions functions heapify, insert, and deleteNode.
class Heap {

    // Convert the list hT into a valid Heap, starting with the
    // node at position i.
    fun heapify(hT: MutableList<Int>, i: Int) {
        var largest = i
        var l = 2 * i + 1
        var r = 2 * i + 2
        if (l < hT.count() && hT.get(l) > hT.get(largest))
            largest = l
        if (r < hT.count() && hT.get(r) > hT.get(largest))
            largest = r

        if (largest != i) {
            val temp = hT.get(largest)
            hT.set(largest, hT.get(i))
            hT.set(i, temp)

            heapify(hT, largest)
        }
    }

    // Adds newNum to the heap, maintaining that hT is a valid
    // heap stored as an array (well, a list).
    fun insert(hT: MutableList<Int>, newNum: Int) {
        val size = hT.count()
        if (size == 0) {
            hT.add(newNum)
        } else {
            hT.add(newNum)
            for (i in (size/2-1) downTo 0) {
                heapify(hT, i)
            }
        }
    }

    // Deletes num from the heap, maintaining that hT is a valid
    // heap stored as an array (well, a list).
    fun deleteNode(hT: MutableList<Int>, num: Int) {
        val size = hT.count()
        var deleteIndex: Int = -1
        for (i in 0..<size) {
            if (num == hT.get(i)) {
                deleteIndex = i
                break
            }
        }

        var temp = hT.get(deleteIndex)
        hT.set(deleteIndex, hT.get(size-1))
        hT.set(size-1, temp)

        hT.remove(size-1)
        for (j in size/2-1 downTo 0)
            heapify(hT, j)
    }
}

// Test our Heap code.
fun main() {
    // Create a list to be the backing for our heap
    val list = mutableListOf<Int>()

    // The heap here is really just a collection of functions
    // (it doesn't really have state itself)
    val h = Heap()
    h.insert(list, 3)
    h.insert(list, 4)
    h.insert(list, 9)
    h.insert(list, 5)
    h.insert(list, 2)

    println("Max-Heap array: ")
    println(list)

    h.deleteNode(list, 4)
    println("After deleting an element: ")
    println(list)
}