Heap Sort in Kotlin

Heap sort is a popular sorting algorithm that works by first creating a binary heap from the array to be sorted and then repeatedly removing the root element of the heap, which is the maximum element, and placing it at the end of the array. The remaining elements in the heap are then reorganized to maintain the heap property, and the process is repeated until all elements have been removed from the heap.

fun heapSort(arr: IntArray) {
    buildHeap(arr)
    for (i in arr.lastIndex downTo 1) {
        swap(arr, 0, i)
        heapify(arr, 0, i)
    }
}

The heapSort function takes an array of integers arr and sorts it in place using heap sort. The function first calls the buildHeap function to create a binary heap from the input array. The function then repeatedly removes the root element of the heap, places it at the end of the array, and reorganizes the remaining elements to maintain the heap property, until all elements have been removed from the heap.

fun buildHeap(arr: IntArray) {
    for (i in arr.indices.reversed()) {
        heapify(arr, i, arr.size)
    }
}

The buildHeap function takes an array of integers arr and creates a binary heap from it. The function iterates through the array from right to left and calls the heapify function on each element to reorganize the heap.

fun heapify(arr: IntArray, index: Int, heapSize: Int) {
    var largest = index
    val left = 2 * index + 1
    val right = 2 * index + 2

    if (left < heapSize && arr[left] > arr[largest]) {
        largest = left
    }

    if (right < heapSize && arr[right] > arr[largest]) {
        largest = right
    }

    if (largest != index) {
        swap(arr, index, largest)
        heapify(arr, largest, heapSize)
    }
}

fun swap(arr: IntArray, i: Int, j: Int) {
    val temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

The heapify function takes an array of integers arr, an index index of an element in the heap, and the size of the heap heapSize, and reorganizes the heap to maintain the heap property. The function finds the largest element among the element at index, its left child, and its right child, and swaps the element at index with the largest element if necessary. The function then recursively calls itself on the largest element to continue reorganizing the heap.

Heap sort has a time complexity of O(n log n), where n is the number of elements in the array, and a space complexity of O(1), as it sorts the array in place. In practice, heap sort is often used for sorting large data sets, as it is more efficient than other sorting algorithms when working with large data sets that do not fit into memory.

fun main() {
    val arr = intArrayOf(20, 15, 81, 12, 6)
	heapSort(arr)
    for(i in 1 until arr.size)
		println(arr[i])
}
fun heapSort(arr: IntArray) {
    buildHeap(arr)
    for (i in arr.lastIndex downTo 1) {
        swap(arr, 0, i)
        heapify(arr, 0, i)
    }
}

fun buildHeap(arr: IntArray) {
    for (i in arr.indices.reversed()) {
        heapify(arr, i, arr.size)
    }
}

fun heapify(arr: IntArray, index: Int, heapSize: Int) {
    var largest = index
    val left = 2 * index + 1
    val right = 2 * index + 2

    if (left < heapSize && arr[left] > arr[largest]) {
        largest = left
    }

    if (right < heapSize && arr[right] > arr[largest]) {
        largest = right
    }

    if (largest != index) {
        swap(arr, index, largest)
        heapify(arr, largest, heapSize)
    }
}

fun swap(arr: IntArray, i: Int, j: Int) {
    val temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}