# 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]
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.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.