Sorting is one of the most important concepts in computer science, and it appears in almost every area of programming — from organizing data to optimizing search performance. Among the many sorting algorithms available, Heap Sort stands out because of its powerful combination of efficiency and reliability. It uses a special tree-like data structure called a heap, which allows it to sort elements quickly without needing extra memory like Merge Sort.
with hands-on learning.
get the skills and confidence to land your next move.
Heap Sort works by first converting an array into a max heap, a structure where the largest element is always at the top. Then, it repeatedly removes the largest element and places it at the end of the array until everything is sorted. This process is both clever and efficient, making Heap Sort an excellent choice for programmers who want to understand how sorting can be done using tree structures. In this article, we’ll explore several ways to implement Heap Sort in Kotlin, including recursive and iterative methods. Everything is explained step-by-step so beginners can follow along easily.
Program 1: Basic Heap Sort Implementation in Kotlin
This first program demonstrates a simple and clear way to implement Heap Sort using a recursive approach to maintain the heap property.
fun heapify(arr: IntArray, n: Int, i: Int) {
var largest = i
val left = 2 * i + 1
val right = 2 * i + 2
if (left < n && arr[left] > arr[largest]) largest = left
if (right < n && arr[right] > arr[largest]) largest = right
if (largest != i) {
val temp = arr[i]
arr[i] = arr[largest]
arr[largest] = temp
heapify(arr, n, largest)
}
}
fun heapSort(arr: IntArray) {
val n = arr.size
for (i in n / 2 - 1 downTo 0) heapify(arr, n, i)
for (i in n - 1 downTo 1) {
val temp = arr[0]
arr[0] = arr[i]
arr[i] = temp
heapify(arr, i, 0)
}
}
fun main() {
val numbers = intArrayOf(12, 11, 13, 5, 6, 7)
println("Original Array: ${numbers.joinToString()}")
heapSort(numbers)
println("Sorted Array: ${numbers.joinToString()}")
}This program starts by building a max heap using the heapify function, which ensures that the largest element is always at the root. Then, it repeatedly swaps the root with the last element, reducing the heap size each time and re-heapifying. It’s a great example of how recursion helps maintain order in a tree-like structure and is often the easiest form for beginners to understand.
Program 2: Heap Sort Using Iteration (Non-Recursive Approach)
Recursion is helpful, but it can sometimes be less efficient for large data sets. This version shows how to perform the same logic using loops instead of recursive calls.
fun heapifyIterative(arr: IntArray, n: Int, i: Int) {
var largest = i
while (true) {
val left = 2 * largest + 1
val right = 2 * largest + 2
var newLargest = largest
if (left < n && arr[left] > arr[newLargest]) newLargest = left
if (right < n && arr[right] > arr[newLargest]) newLargest = right
if (newLargest == largest) break
val temp = arr[largest]
arr[largest] = arr[newLargest]
arr[newLargest] = temp
largest = newLargest
}
}
fun heapSortIterative(arr: IntArray) {
val n = arr.size
for (i in n / 2 - 1 downTo 0) heapifyIterative(arr, n, i)
for (i in n - 1 downTo 1) {
val temp = arr[0]
arr[0] = arr[i]
arr[i] = temp
heapifyIterative(arr, i, 0)
}
}
fun main() {
val numbers = intArrayOf(4, 10, 3, 5, 1)
println("Original Array: ${numbers.joinToString()}")
heapSortIterative(numbers)
println("Sorted Array: ${numbers.joinToString()}")
}Here, the logic remains the same as the recursive version, but instead of calling heapify again, we use a while loop to adjust the heap. This approach avoids stack overflow risks in very large data sets and gives beginners insight into how recursive logic can often be transformed into iterative logic using loops.
Program 3: Heap Sort in Descending Order
Sometimes we need to sort elements in descending order instead of ascending. This version shows how to modify the heap to create a min heap, ensuring the smallest element is always on top.
fun minHeapify(arr: IntArray, n: Int, i: Int) {
var smallest = i
val left = 2 * i + 1
val right = 2 * i + 2
if (left < n && arr[left] < arr[smallest]) smallest = left
if (right < n && arr[right] < arr[smallest]) smallest = right
if (smallest != i) {
val temp = arr[i]
arr[i] = arr[smallest]
arr[smallest] = temp
minHeapify(arr, n, smallest)
}
}
fun heapSortDescending(arr: IntArray) {
val n = arr.size
for (i in n / 2 - 1 downTo 0) minHeapify(arr, n, i)
for (i in n - 1 downTo 1) {
val temp = arr[0]
arr[0] = arr[i]
arr[i] = temp
minHeapify(arr, i, 0)
}
}
fun main() {
val numbers = intArrayOf(15, 20, 5, 30, 10)
println("Original Array: ${numbers.joinToString()}")
heapSortDescending(numbers)
println("Sorted in Descending Order: ${numbers.joinToString()}")
}By making a few changes in the comparisons, we can easily convert a max heap into a min heap, which gives us a descending order result. This helps beginners understand how flexible the Heap Sort algorithm is and how simple changes in comparison logic can completely reverse the sorting order.
Program 4: Heap Sort Using Kotlin Collections
Kotlin’s modern features allow us to write cleaner and more expressive code. In this version, we use a MutableList instead of an array, showing how Heap Sort can work with Kotlin’s collection framework.
fun heapifyList(list: MutableList<Int>, n: Int, i: Int) {
var largest = i
val left = 2 * i + 1
val right = 2 * i + 2
if (left < n && list[left] > list[largest]) largest = left
if (right < n && list[right] > list[largest]) largest = right
if (largest != i) {
val temp = list[i]
list[i] = list[largest]
list[largest] = temp
heapifyList(list, n, largest)
}
}
fun heapSortList(list: MutableList<Int>) {
val n = list.size
for (i in n / 2 - 1 downTo 0) heapifyList(list, n, i)
for (i in n - 1 downTo 1) {
val temp = list[0]
list[0] = list[i]
list[i] = temp
heapifyList(list, i, 0)
}
}
fun main() {
val numbers = mutableListOf(9, 4, 7, 1, 3, 6)
println("Original List: $numbers")
heapSortList(numbers)
println("Sorted List: $numbers")
}Using Kotlin’s MutableList makes the program more flexible, as lists are easier to modify and manage. The algorithm’s logic remains the same, but now you can use Kotlin’s collection functions alongside Heap Sort logic. This version is great for developers who prefer working with collections over arrays.
Frequently Asked Questions (FAQ)
Below are some common questions learners ask when studying Heap Sort in Kotlin.
Q1: What is Heap Sort in Kotlin?
Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It works by repeatedly extracting the largest element from the heap and placing it at the end of the array.
Q2: Is Heap Sort faster than Quick Sort?
In most practical cases, Quick Sort is faster. However, Heap Sort guarantees a time complexity of O(n log n) in all cases, while Quick Sort can degrade to O(n²) in the worst case.
Q3: Does Heap Sort require extra memory?
No, Heap Sort sorts elements in place, which means it doesn’t require additional memory for another array or list.
Q4: What is the difference between a max heap and a min heap?
A max heap keeps the largest element at the root, while a min heap keeps the smallest element at the root.
Q5: Can Heap Sort handle negative numbers?
Yes, Heap Sort works perfectly fine with negative numbers as it only compares values, regardless of their sign.
Conclusion
Heap Sort is one of the most efficient and reliable sorting algorithms that every Kotlin programmer should learn. It not only helps you understand how heaps work but also teaches you how sorting can be achieved using tree structures instead of simple loops or recursion. Whether you use recursion, iteration, or Kotlin’s modern collections, the logic of Heap Sort remains elegant and powerful.
The best way to master Heap Sort is through practice. Try modifying these programs, experiment with different inputs, and see how the algorithm behaves. Once you get comfortable with Heap Sort, you’ll have a deeper appreciation for how sorting algorithms work and how Kotlin can make them look clean and easy to understand.
