Heaps and Prefix Median Computation in Kotlin

Introduction

Hello there, budding programmer! I hope you're ready because today, we're going to dive deep into high-level data manipulation and increase our understanding of heaps . Heaps are fundamental data structures commonly used in algorithms. We're going to leverage their potential today in an interesting algorithmic problem. Are you ready for the challenge? Let's get started!

Task Statement

1

Heap and Its Operations

A heap is a useful tool in Kotlin that helps efficiently organize and retrieve data based on their values. In our context, we use two specific types of heaps: a Min Heap and a Max Heap . The Min Heap is used to store the larger half of the numbers seen so far, while the Max Heap stores the smaller half. In Kotlin, we can implement heaps using the PriorityQueue class from the Java standard library. For our task, we'll be using these principal operations: Adding Elements : You can add a new element to a heap using the add() method. A PriorityQueue in Kotlin by default acts as a Min Heap. To create a Max Heap, you can use a custom comparator that reverses the ordering. Kotlin import java.util.PriorityQueue val minHeap = PriorityQueue<Int>() val maxHeap = PriorityQueue<Int>(compareByDescending { it }) Removing Elements : The poll() method removes the top element from the heap, which is the smallest element in the Min Heap or the largest element in the Max Heap. Accessing Minimum Element : The peek() method is used to inspect the root element of the heap without removing it. For the Min Heap, peek() will return the smallest element. These operations ensure that the root element can always be gathered quickly, in constant time O(1), and new elements can be added while maintaining the heap structure in logarithmic time, O(log n) .

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

Kotlin

import java.util.*

fun prefixMedian(arr: IntArray): IntArray {
    val minHeap = PriorityQueue<Int>()
    val maxHeap = PriorityQueue<Int>(compareByDescending { it })
    val medians = IntArray(arr.size)
}

Kotlin

import java.util.*

fun prefixMedian(arr: IntArray): IntArray {
    val minHeap = PriorityQueue<Int>()
    val maxHeap = PriorityQueue<Int>(compareByDescending { it })
    val medians = IntArray(arr.size)

    for (num in arr) {
        if (maxHeap.isNotEmpty() && num < maxHeap.peek()) {
            maxHeap.add(num)
        } else {
            minHeap.add(num)
        }
    }
}

Kotlin

import java.util.*

fun prefixMedian(arr: IntArray): IntArray {
    val minHeap = PriorityQueue<Int>()
    val maxHeap = PriorityQueue<Int>(compareByDescending { it })
    val medians = IntArray(arr.size)

    for (num in arr) {
        if (maxHeap.isNotEmpty() && num < maxHeap.peek()) {
            maxHeap.add(num)
        } else {
            minHeap.add(num)
        }

        if (maxHeap.size > minHeap.size) {
            minHeap.add(maxHeap.poll())
        } else if (minHeap.size > maxHeap.size + 1) {
            maxHeap.add(minHeap.poll())
        }
    }
}

Kotlin

import java.util.*

fun prefixMedian(arr: IntArray): IntArray {
    val minHeap = PriorityQueue<Int>()
    val maxHeap = PriorityQueue<Int>(compareByDescending { it })
    val medians = IntArray(arr.size)

    for (i in arr.indices) {
        val num = arr[i]
        if (maxHeap.isNotEmpty() && num < maxHeap.peek()) {
            maxHeap.add(num)
        } else {
            minHeap.add(num)
        }

        if (maxHeap.size > minHeap.size) {
            minHeap.add(maxHeap.poll())
        } else if (minHeap.size > maxHeap.size + 1) {
            maxHeap.add(minHeap.poll())
        }

        medians[i] = if (minHeap.size == maxHeap.size) {
            maxHeap.peek()
        } else {
            minHeap.peek()
        }
    }

    return medians
}

fun main() {
    val arr = intArrayOf(1, 9, 2, 8, 3)
    val medians = prefixMedian(arr)

    println("Final Medians Array: ${medians.joinToString()}")
}

Introduction

Task Statement

Heap and Its Operations

Join the 1M+ learners on CodeSignal

Solution Building: Step 1

Solution Building: Step 2

Solution Building: Step 3

Solution Building: Step 4

Lesson Summary