Min Heap to Max Heap in Kotlin

To convert a min heap into a max heap, you can follow these steps:

1. Traverse the min heap from the last non-leaf node to the root. For a complete binary tree, the last non-leaf node is the parent of the last leaf node.
2. For each node, swap its value with the larger of its children. This ensures that the node’s value is greater than or equal to its children’s values.
3. Repeat step 2 for each parent node, moving up the tree.
4. Once you have traversed the entire tree, the min heap will be converted into a max heap.

fun minHeapToMaxHeap(heap: IntArray) {
    val n = heap.size
    val lastNonLeaf = (n / 2) - 1

    for (i in lastNonLeaf downTo 0) {
        val leftChild = (2 * i) + 1
        val rightChild = (2 * i) + 2

        if (leftChild < n && heap[leftChild] > heap[i]) {
            val temp = heap[i]
            heap[i] = heap[leftChild]
            heap[leftChild] = temp
        }

        if (rightChild < n && heap[rightChild] > heap[i]) {
            val temp = heap[i]
            heap[i] = heap[rightChild]
            heap[rightChild] = temp
        }
    }
}
fun main() {
    val heap = intArrayOf(2, 3, 5, 8, 10, 6)

    println("Min heap: ${heap.contentToString()}")
    minHeapToMaxHeap(heap)
    println("Max heap: ${heap.contentToString()}")
}

The minHeapToMaxHeap function takes an array of integers representing a min heap as input. It initializes the length of the array to n and calculates the index of the last non-leaf node in the heap as (n / 2) - 1. This is because all nodes after this index are leaf nodes and do not have any children to swap with.

The function then starts a loop that iterates from the last non-leaf node down to the root node (index 0). For each iteration, it calculates the indices of the left and right children of the current node using the formula (2 * i) + 1 and (2 * i) + 2, respectively.

For each node, the function checks if the left child’s value is greater than the node’s value. If so, it swaps the values of the node and the left child. It then checks if the right child’s value is greater than the node’s value. If so, it swaps the values of the node and the right child.

The loop continues until all parent nodes have been swapped with their larger child nodes. At the end of the function, the input heap array will be transformed into a max heap.

This will output:

Min heap: [2, 3, 5, 8, 10, 6]
Max heap: [10, 8, 5, 2, 3, 6]