Lesson 4
Finding Prefix Medians Using Heaps in Ruby
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 an array of unique integers with elements ranging from 1 to 10610^6 and a length between 1 to 1000, we need to create a Ruby method prefix_median. This method will take the array as input and return a corresponding array, which consists of the medians of all the prefixes of the input array.

Remember that a prefix of an array is a contiguous subsequence that starts from the first element. And 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 array [1, 9, 2, 8, 3]. The output of your method should be [1, 5, 2, 5, 3].

Heap and Its Operations

Ruby provides several options to implement a heap through libraries like algorithms, which include heap data structures. In our task, we'll use these structures to manage our data efficiently.

In our context, we use a specific type of heap called a Min Heap, where the smallest element is located at the root. Additionally, we have a Max Heap, which stores the largest element at the root.

For our task, we'll be using these principal operations:

  • Adding Elements: You can add a new element to a heap using the push method.

  • Removing Elements: Use the pop method to remove and return the smallest or largest element from the heap.

  • Accessing Minimum/Maximum Element: Use min or max to look at the smallest or largest element without removing it from the heap.

These operations ensure efficient organization and retrieval, allowing the smallest or largest element to be gathered quickly.

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 an array to store the median for each prefix.

Ruby
1require 'algorithms' 2 3include Containers 4 5def prefix_median(arr) 6 min_heap = MinHeap.new 7 max_heap = MaxHeap.new 8 medians = [] 9end
Solution Building: Step 2

As the next step, we will sequentially take each number from the array and, depending on its value, push it into the min_heap or the max_heap. If it is smaller than the maximum of the lower half, it will go into the max_heap. Otherwise, it will go into the min_heap.

Ruby
1def prefix_median(arr) 2 min_heap = MinHeap.new 3 max_heap = MaxHeap.new 4 medians = [] 5 6 arr.each do |num| 7 if !max_heap.empty? && num < max_heap.max 8 max_heap.push(num) 9 else 10 min_heap.push(num) 11 end 12 end 13end
Solution Building: Step 3

Next, we need to balance the two heaps to ensure that the difference between their sizes is never more than one. This way, we can always have quick access to the median. If the max_heap size becomes larger than the min_heap, we pop the max_heap's top element and push it to the min_heap. If the min_heap becomes more than one element larger than the max_heap, we do the reverse.

Ruby
1def prefix_median(arr) 2 min_heap = MinHeap.new 3 max_heap = MaxHeap.new 4 medians = [] 5 6 arr.each do |num| 7 if !max_heap.empty? && num < max_heap.max 8 max_heap.push(num) 9 else 10 min_heap.push(num) 11 end 12 13 if max_heap.size > min_heap.size 14 min_heap.push(max_heap.pop) 15 elsif min_heap.size > max_heap.size + 1 16 max_heap.push(min_heap.pop) 17 end 18 end 19end
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 max_heap and min_heap, and then append it to our array of medians.

Ruby
1def prefix_median(arr) 2 min_heap = MinHeap.new 3 max_heap = MaxHeap.new 4 medians = [] 5 6 arr.each do |num| 7 if !max_heap.empty? && num < max_heap.max 8 max_heap.push(num) 9 else 10 min_heap.push(num) 11 end 12 13 if max_heap.size > min_heap.size 14 min_heap.push(max_heap.pop) 15 elsif min_heap.size > max_heap.size + 1 16 max_heap.push(min_heap.pop) 17 end 18 19 if min_heap.size == max_heap.size 20 medians << (max_heap.max + min_heap.min) / 2.0 21 else 22 medians << min_heap.min 23 end 24 end 25 26 medians 27end

Voilà! You have successfully implemented a method that solves the problem using heaps in Ruby.

Lesson Summary

Congratulations! You've successfully tackled an interesting algorithmic problem using heaps for array manipulation in Ruby. The solution you've created not only employs heaps but also showcases your understanding of how to efficiently manage and interpret array elements using Ruby's data structures.

In the next session, you'll be given additional problems to solve. This will encourage you to use heaps and array manipulations fluently, helping you consolidate your understanding of today's lesson. Keep practicing, and remember — practice makes perfect. Happy coding!

Enjoy this lesson? Now it's time to practice with Cosmo!
Practice is how you turn knowledge into actual skills.