Heap sort in kotlin
Algorithms #algorithms #sorting #heap- Lean about internal workings of heap here
In heap sort, all values are stored in a heap and removed one by one. Depending the type of heap (min/max) the removed elements
will be in sorted order. For max heap, the elements will be sorted in descending order as at any point in time the heap root will contain
the maximum value as its root. Similarly, for min heap, the elements will be sorted in natural order.
- Ascending order example
import java.util.*
fun main() {
val sortedList = mutableListOf<Int>()
val minHeap = PriorityQueue<Int>()
minHeap.add(30)
minHeap.add(10)
minHeap.add(40)
while (minHeap.isNotEmpty()) {
sortedList.add(minHeap.poll())
}
println(sortedList) // [10, 30, 40]
}
- Descending order example
import java.util.*
fun main() {
val sortedList = mutableListOf<Int>()
val maxHeap = PriorityQueue<Int>(Collections.reverseOrder())
maxHeap.add(30)
maxHeap.add(10)
maxHeap.add(40)
while (maxHeap.isNotEmpty()) {
sortedList.add(maxHeap.poll())
}
println(sortedList) // [40, 30, 10]
}
Time complexity
Heap sort runs in nlog(n) time. For a heap of n elments, insertion will take nlog(n) time while remove the items will also
take nlog(n) time. So, the total time for heap sort is equal to nlog(n) + nlog(n) = 2nlog(n) which is O(nlogn)