Lesson 4

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!

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 $10^6$ and length between $1$ to $1000$, we need to create a JavaScript function `prefixMedian()`

. This function 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. 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 the element in the position `length / 2 - 1`

.

For example, consider an input array `[1, 9, 2, 8, 3]`

. The output of your function should be `[1, 1, 2, 2, 3]`

.

A heap is a specialized binary tree-based data structure that satisfies the heap property: for a Min Heap, every parent node is less than or equal to its child nodes; for a Max Heap, every parent node is greater than or equal to its child nodes. This property makes heaps particularly efficient for operations like finding the minimum or maximum value.

In practice, heaps can be implemented using arrays. For a given node at index `i`

in an array:

- Its left child is at index
`2 * i + 1`

- Its right child is at index
`2 * i + 2`

- Its parent is at index
`Math.floor((i - 1) / 2)`

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. JavaScript does not have built-in heap functionality, so we will implement one or use an external library.

Here, we'll use simple custom implementations for `MinHeap`

and `MaxHeap`

.

To make the functions easier to understand, let's define our `MinHeap`

and `MaxHeap`

classes first. We will use negation to simulate a `MaxHeap`

with `MinHeap`

operations.

JavaScript`1class MinHeap { 2 constructor() { 3 this.heap = []; 4 } 5 6 add(value) { 7 this.heap.push(value); 8 this._heapifyUp(); 9 } 10 11 poll() { 12 if (this.size() === 0) return null; 13 if (this.size() <= 1) return this.heap.pop(); 14 const root = this.heap[0]; 15 this.heap[0] = this.heap.pop(); 16 this._heapifyDown(); 17 return root; 18 } 19 20 peek() { 21 return this.heap[0]; 22 } 23 24 size() { 25 return this.heap.length; 26 } 27 28 _heapifyUp() { 29 let index = this.heap.length - 1; 30 while (index > 0) { 31 const parentIndex = Math.floor((index - 1) / 2); 32 if (this.heap[parentIndex] <= this.heap[index]) break; 33 [this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]]; 34 index = parentIndex; 35 } 36 } 37 38 _heapifyDown() { 39 let index = 0; 40 while (2 * index + 1 < this.heap.length) { 41 let leftChildIndex = 2 * index + 1; 42 let rightChildIndex = 2 * index + 2; 43 let swapIndex = leftChildIndex; 44 45 if (rightChildIndex < this.heap.length) { 46 if (this.heap[rightChildIndex] < this.heap[leftChildIndex]) { 47 swapIndex = rightChildIndex; 48 } 49 } 50 51 if (this.heap[index] <= this.heap[swapIndex]) break; 52 53 [this.heap[index], this.heap[swapIndex]] = [this.heap[swapIndex], this.heap[index]]; 54 index = swapIndex; 55 } 56 } 57} 58 59class MaxHeap extends MinHeap { 60 add(value) { 61 super.add(-value); 62 } 63 64 poll() { 65 return -super.poll(); 66 } 67 68 peek() { 69 return -super.peek(); 70 } 71}`

The `MinHeap`

class defines a min-heap with methods to add elements (`add`

), remove and return the smallest element (`poll`

), get the smallest element without removing it (`peek`

), and get the heap size (`size`

). The methods `_heapifyUp`

and `_heapifyDown`

maintain the heap property after adding or removing elements, respectively. The `MaxHeap`

class extends `MinHeap`

by using negation to maintain a max-heap; it overrides the `add`

, `poll`

, and `peek`

methods to negate the values, effectively turning the min-heap operations into max-heap operations.

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. Now, let's initialize these.

JavaScript`1function prefixMedian(arr) { 2 const minHeap = new MinHeap(); 3 const maxHeap = new MaxHeap(); 4 const medians = new Array(arr.length); 5}`

This snippet initializes two heap instances, `minHeap`

and `maxHeap`

, to store the larger and smaller halves of the numbers, respectively. It also creates an array `medians`

of the same length as the input array to store the medians of each prefix.

As the next step, we will sequentially take each number from the array 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`

.

JavaScript`1function prefixMedian(arr) { 2 const minHeap = new MinHeap(); 3 const maxHeap = new MaxHeap(); 4 const medians = new Array(arr.length); 5 6 for (const num of arr) { 7 if (maxHeap.size() > 0 && num < maxHeap.peek()) { 8 maxHeap.add(num); 9 } else { 10 minHeap.add(num); 11 } 12 } 13}`

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 `maxHeap`

size becomes larger than the `minHeap`

, we poll the `maxHeap`

's top element and add it to the `minHeap`

. If the `minHeap`

becomes more than one element larger than the `maxHeap`

, we do the reverse.

JavaScript`1function prefixMedian(arr) { 2 const minHeap = new MinHeap(); 3 const maxHeap = new MaxHeap(); 4 const medians = new Array(arr.length); 5 6 for (let i = 0; i < arr.length; i++) { 7 const num = arr[i]; 8 if (maxHeap.size() > 0 && num < maxHeap.peek()) { 9 maxHeap.add(num); 10 } else { 11 minHeap.add(num); 12 } 13 14 if (maxHeap.size() > minHeap.size()) { 15 minHeap.add(maxHeap.poll()); 16 } else if (minHeap.size() > maxHeap.size() + 1) { 17 maxHeap.add(minHeap.poll()); 18 } 19 } 20}`

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 array of medians.

JavaScript`1function prefixMedian(arr) { 2 const minHeap = new MinHeap(); 3 const maxHeap = new MaxHeap(); 4 const medians = new Array(arr.length); 5 6 for (let i = 0; i < arr.length; i++) { 7 const num = arr[i]; 8 if (maxHeap.size() > 0 && num < maxHeap.peek()) { 9 maxHeap.add(num); 10 } else { 11 minHeap.add(num); 12 } 13 14 if (maxHeap.size() > minHeap.size()) { 15 minHeap.add(maxHeap.poll()); 16 } else if (minHeap.size() > maxHeap.size() + 1) { 17 maxHeap.add(minHeap.poll()); 18 } 19 20 if (minHeap.size() === maxHeap.size()) { 21 medians[i] = maxHeap.peek(); 22 } else { 23 medians[i] = minHeap.peek(); 24 } 25 } 26 27 return medians; 28} 29 30// Test the function 31const arr = [1, 9, 2, 8, 3]; 32const medians = prefixMedian(arr); 33console.log("Final Medians Array: ", medians); // Output: Final Medians Array: [ 1, 1, 2, 2, 3 ]`

After balancing the heaps, this snippet computes the median for each prefix and stores it in the `medians`

array. If the sizes of both heaps are equal, the median is the root of the `maxHeap`

; otherwise, it's the root of the `minHeap`

. The final `medians`

array is returned and tested with an example input.

Congratulations! You've successfully tackled an interesting algorithmic problem that required the use of heaps for array manipulation in JavaScript. The solution you've created not only uses heaps but also demonstrates your understanding of array hierarchies and the meaningful interpretation of numerical values.

In the next session, you'll be given more similar 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!