// Adapted from https://runestone.academy/ns/books/published/kotlinds/trees_binary-heap-implementation.html?mode=browsing

class Heap<E: Comparable<E>>() {

    var heap = mutableListOf<E>()

    constructor(nonHeap: List<E>): this() {
        heapify(nonHeap)
    }

    private fun heapify(nonHeap: List<E>) {
        if (nonHeap.count() > 0) {
            heap = nonHeap.toMutableList()  // copies list

            var currIndex = heap.count() / 2 - 1
            while (currIndex >= 0) {
                percolateDown(currIndex)
                currIndex -= 1
            }
        }
    }

    private fun swapItemsAt(index1: Int, index2: Int) {
        val temporary = heap[index1]
        heap[index1] = heap[index2]
        heap[index2] = temporary
    }

    private fun percolateUp(index: Int) {
        var index = index
        while (index > 0) {
            val parentIndex = (index - 1) / 2
            if (heap[index] < heap[parentIndex]) {
                swapItemsAt(index, parentIndex)
            }
            index = parentIndex
        }
    }

    fun insert(element: E) {
        heap.add(element)
        percolateUp(heap.count() - 1)
    }

    fun percolateDown(index: Int) {
        var index = index
        while (2 * index + 1 < heap.count()) {
            val smallerChild = getSmallerChild(index)
            if (heap[index] > heap[smallerChild]) {
                swapItemsAt(index, smallerChild)
            } else {
                break
            }
            index = smallerChild
        }
    }

    fun getSmallerChild(index: Int): Int {
        if (2 * index + 2 > heap.count() - 1) {
            return 2 * index + 1
        }
        if (heap[2 * index + 1] < heap[2 * index + 2]) {
            return 2 * index + 1
        }
        return 2 * index + 2
    }

    fun delete(): E? {
        if (heap.count() == 0) {
            return null
        }

        val result = heap[0]
        swapItemsAt(0, heap.count() - 1)
        heap.removeLast()
        percolateDown(0)
        return result
    }

    fun peek(): E? {
        if (heap.count() == 0) {
            return null
        } else {
            return heap[0]
        }
    }

    fun isEmpty(): Boolean {
        return heap.count()==0
    }

    fun size(): Int {
        return heap.count()
    }

    override fun toString(): String {
        return heap.toString()
    }

}