Prefix Medians with Heaps

Prefix Medians with Heaps | CodeSignal Learn

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

We have a task at hand related to array manipulation and the use of heaps . The task is as follows: Given a list of unique integers with elements ranging from 1 to 10^6 and length between 1 and 1000, we need to create a Scala function prefixMedian . This function will take the list as input and return a corresponding list, which consists of the medians of all the prefixes of the input list. Remember that a prefix of an array is a contiguous subsequence that starts from the first element. The median of a sequence of numbers is the middle number when the sequence is sorted. If the length of the sequence is even, the median is half the sum of the middle two elements. For example, consider an input list List(1, 9, 2, 8, 3) . The output of your function should be List(1, 5.0, 2, 5.0, 3) .

Heap and Its Operations

Join the 1M+ learners on CodeSignal

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

Solution Building: Step 1

Alright, let's break our approach down into manageable steps. To begin with, we're going to need two heaps: a min-heap to store the larger half of the numbers seen so far, and a max-heap to store the smaller half. We'll also need a list to store the median for each prefix. Let's initialize these in Scala: Scala import scala.collection.mutable.PriorityQueue def prefixMedian(arr: List[Int]): List[Double] = {// Max-heap for the lower half val maxHeap = PriorityQueue.empty[Int] // Min-heap for the upper half (using reversed ordering) val minHeap = PriorityQueue.empty[Int](Ordering.Int.reverse) val medians = scala.collection.mutable.ListBuffer.empty[Double] // ... (rest of the code will follow)} import scala.collection.mutable.PriorityQueue def prefixMedian(arr: List[Int]): List[Double] = {// Max-heap for the lower half val maxHeap = PriorityQueue.empty[Int] // Min-heap for the upper half (using reversed ordering) val minHeap = PriorityQueue.empty[Int](Ordering.Int.reverse) val medians = scala.collection.mutable.ListBuffer.empty[Double] // ... (rest of the code will follow)}

Solution Building: Step 2

Next, we will sequentially take each number from the list and, depending on its value, push it into the minHeap or the maxHeap . If it is smaller than the maximum of the lower half, it will go into the maxHeap . Otherwise, it will go into the minHeap . In Scala, to simulate a max-heap, we use the default PriorityQueue . For the min-heap, we use Ordering.Int.reverse to reverse the order. Scala import scala.collection.mutable.PriorityQueue def prefixMedian(arr: List[Int]): List[Double] = {val maxHeap = PriorityQueue.empty[Int] val minHeap = PriorityQueue.empty[Int](Ordering.Int.reverse) val medians = scala.collection.mutable.ListBuffer.empty[Double] for (num <- arr) {if (maxHeap.nonEmpty && num < maxHeap.head) {maxHeap.enqueue(num)} else {minHeap.enqueue(num)} // ... (balancing and median calculation will follow)} // ...} import scala.collection.mutable.PriorityQueue def prefixMedian(arr: List[Int]): List[Double] = {val maxHeap = PriorityQueue.empty[Int] val minHeap = PriorityQueue.empty[Int](Ordering.Int.reverse) val medians = scala.collection.mutable.ListBuffer.empty[Double] for (num <- arr) {if (maxHeap.nonEmpty && num < maxHeap.head) {maxHeap.enqueue(num)} else {minHeap.enqueue(num)} // ... (balancing and median calculation will follow)} // ...}

Solution Building: Step 3

Now, we need to balance the two heaps to ensure that the difference between their sizes is never more than one. If the maxHeap size becomes larger than the minHeap, we move the top element from maxHeap to minHeap . If the minHeap becomes more than one element larger than the maxHeap, we do the reverse. Scala import scala.collection.mutable.PriorityQueue def prefixMedian(arr: List[Int]): List[Double] = {val maxHeap = PriorityQueue.empty[Int] val minHeap = PriorityQueue.empty[Int](Ordering.Int.reverse) val medians = scala.collection.mutable.ListBuffer.empty[Double] for (num <- arr) {if (maxHeap.nonEmpty && num < maxHeap.head) {maxHeap.enqueue(num)} else {minHeap.enqueue(num)} // Balance the heaps if (maxHeap.size > minHeap.size) {minHeap.enqueue(maxHeap.dequeue())} else if (minHeap.size > maxHeap.size + 1) {maxHeap.enqueue(minHeap.dequeue())} // ... (median calculation will follow)} // ...} import scala.collection.mutable.PriorityQueue def prefixMedian(arr: List[Int]): List[Double] = {val maxHeap = PriorityQueue.empty[Int] val minHeap = PriorityQueue.empty[Int](Ordering.Int.reverse) val medians = scala.collection.mutable.ListBuffer.empty[Double] for (num <- arr) {if (maxHeap.nonEmpty && num < maxHeap.head) {maxHeap.enqueue(num)} else {minHeap.enqueue(num)} // Balance the heaps if (maxHeap.size > minHeap.size) {minHeap.enqueue(maxHeap.dequeue())} else if (minHeap.size > maxHeap.size + 1) {maxHeap.enqueue(minHeap.dequeue())} // ... (median calculation will follow)} // ...}

Solution Building: Step 4

Having balanced the heaps, we've set ourselves up for the effortless retrieval of the median. We compute the median based on the elements at the top of the maxHeap and minHeap, and then append it to our list of medians. Scala import scala.collection.mutable.PriorityQueue def prefixMedian(arr: List[Int]): List[Double] = {val maxHeap = PriorityQueue.empty[Int] val minHeap = PriorityQueue.empty[Int](Ordering.Int.reverse) val medians = scala.collection.mutable.ListBuffer.empty[Double] for (num <- arr) {if (maxHeap.nonEmpty && num < maxHeap.head) {maxHeap.enqueue(num)} else {minHeap.enqueue(num)} // Balance the heaps if (maxHeap.size > minHeap.size) {minHeap.enqueue(maxHeap.dequeue())} else if (minHeap.size > maxHeap.size + 1) {maxHeap.enqueue(minHeap.dequeue())} // Calculate the median if (minHeap.size == maxHeap.size) {val median = (minHeap.head + maxHeap.head) / 2.0 medians.append(median)} else {medians.append(minHeap.head.toDouble)}} medians.toList} import scala.collection.mutable.PriorityQueue def prefixMedian(arr: List[Int]): List[Double] = {val maxHeap = PriorityQueue.empty[Int] val minHeap = PriorityQueue.empty[Int](Ordering.Int.reverse) val medians = scala.collection.mutable.ListBuffer.empty[Double] for (num <- arr) {if (maxHeap.nonEmpty && num < maxHeap.head) {maxHeap.enqueue(num)} else {minHeap.enqueue(num)} // Balance the heaps if (maxHeap.size > minHeap.size) {minHeap.enqueue(maxHeap.dequeue())} else if (minHeap.size > maxHeap.size + 1) {maxHeap.enqueue(minHeap.dequeue())} // Calculate the median if (minHeap.size == maxHeap.size) {val median = (minHeap.head + maxHeap.head) / 2.0 medians.append(median)} else {medians.append(minHeap.head.toDouble)}} medians.toList} For example, calling prefixMedian(List(1, 9, 2, 8, 3)) will return List(1.0, 5.0, 2.0, 5.0, 3.0) .

Prefix Medians with Heaps

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