Heap Data Structure Implementation in Kotlin

1. Introduction

A Heap is a specialized tree-based data structure that satisfies the heap property. In a max heap, for any given node I, the value of I is greater than or equal to the values of its children. Conversely, in a min heap, the value of I is less than or equal to the values of its children. Heaps are crucial in algorithms like heap sort and for data structures like priority queues. 

In this post, we'll discuss a Heap implementation in Kotlin, distinguishing between min-heap and max-heap operations.

2. Implementation Steps

1. Define the Heap class.

2. Maintain an internal list to store heap elements.

3. Implement helper methods for navigating the tree: parent, left child, and right child.

4. Implement methods for adding an element, removing the peak, and heapify.

5. Implement methods for displaying the heap.

3. Implementation in Kotlin Programming

class Heap(private val isMinHeap: Boolean = true) {
    private val list = mutableListOf<Int>()
    
    // Helper functions
    private fun parent(index: Int) = (index - 1) / 2
    
    private fun leftChild(index: Int) = 2 * index + 1
    
    private fun rightChild(index: Int) = 2 * index + 2
    
    // Compare based on heap type
    private fun compare(i: Int, j: Int) = if (isMinHeap) list[i] < list[j] else list[i] > list[j]
    fun add(value: Int) {
        list.add(value)
        var currentIndex = list.size - 1
        while (currentIndex > 0 && compare(currentIndex, parent(currentIndex))) {
            val temp = list[currentIndex]
            list[currentIndex] = list[parent(currentIndex)]
            list[parent(currentIndex)] = temp
            currentIndex = parent(currentIndex)
        }
    }
    
    fun removePeak(): Int {
        if (list.isEmpty()) throw NoSuchElementException("Heap is empty")
        val peak = list[0]
        val lastValue = list.removeAt(list.size - 1)
        if (list.isNotEmpty()) {
            list[0] = lastValue
            heapify(0)
        }
        return peak
    }
    
    private fun heapify(index: Int) {
        val left = leftChild(index)
        val right = rightChild(index)
        var largestOrSmallest = index
        if (left < list.size && compare(left, index)) largestOrSmallest = left
        if (right < list.size && compare(right, largestOrSmallest)) largestOrSmallest = right
        if (largestOrSmallest != index) {
            val temp = list[index]
            list[index] = list[largestOrSmallest]
            list[largestOrSmallest] = temp
            heapify(largestOrSmallest)
        }
    }
    
    fun display() {
        println(list)
    }
    
}


// client code to test Heap Data Structure Implementation in Kotlin
fun main() {
    val minHeap = Heap()
    val maxHeap = Heap(isMinHeap = false)
    listOf(5, 3, 8, 1, 4).forEach {
        minHeap.add(it)
        maxHeap.add(it)
    }
    minHeap.display()
    maxHeap.display()
    println("Min peak: ${minHeap.removePeak()}")
    println("Max peak: ${maxHeap.removePeak()}")
    minHeap.display()
    maxHeap.display()
}

Output:

[1, 3, 8, 5, 4]
[8, 5, 3, 1, 4]
Min peak: 1
Max peak: 8
[3, 4, 8, 5]
[5, 4, 3]

Explanation:

1. Heap class: Represents either a min-heap or a max-heap.

2. isMinHeap: A flag that indicates if the current instance is a min-heap (default) or a max-heap.

3. Helper methods: Provide quick access to a node's parent, leftChild, and rightChild.

4. compare method: Compares two nodes based on whether it's a min-heap or max-heap.

5. add method: Adds a new value to the heap while maintaining the heap property.

6. removePeak method: Removes the peak element (smallest for min-heap, largest for max-heap) and maintains the heap property.

7. heapify method: Rebalances the heap from a given index.

8. The main function demonstrates adding elements to both min and max heaps, displaying them, removing peaks, and then displaying them again.