Sliding Window Median 🎯

Welcome to our in-depth guide on the Sliding Window Median! In this lesson, we'll explore how to calculate the median of a data stream using the sliding window technique. This concept is crucial for real-time data processing and machine learning applications. Let's dive in!

Understanding Median 💡

Before we delve into the sliding window median, let's first understand what a median is. The median is the middle value in a sorted list of numbers. If the list has an odd number of observations, the median is the middle number. If it has an even number of observations, the median is the average of the two middle numbers.

The Concept of Sliding Window 📝

A sliding window is a data structure that moves through a data stream, analyzing a fixed-size window of data at a time. This is particularly useful when dealing with large data streams where we want to analyze data in real-time or with a moving window.

Combining Median and Sliding Window ✅

The Sliding Window Median is a technique that applies the concept of a median to a sliding window. It allows us to find the median of a data stream as it moves through the stream, maintaining efficiency even with large data sets.

Real-World Applications 🎯

Sliding Window Median is used in various real-world scenarios, including:

Real-time stock price analysis
Anomaly detection in network traffic
Online machine learning algorithms

Implementation 💡

For our implementation, we'll use a Min Heap (Max Heap for maintaining the lower half of the data) to efficiently manage the sliding window.

Code Example 1 - Min Heap Implementation 📝

python

class MinHeap:
    def __init__(self):
        self.heap = []

    def insert(self, value):
        self.heap.append(value)
        self._bubbleUp(len(self.heap) - 1)

    def _bubbleUp(self, index):
        parent = index // 2
        while index > 1 and self.heap[parent] > self.heap[index]:
            self.heap[parent], self.heap[index] = self.heap[index], self.heap[parent]
            index = parent
            parent = index // 2

    def getMedian(self):
        if len(self.heap) % 2 == 0:
            return (self.heap[1] + self.heap[len(self.heap) // 2]) / 2
        else:
            return self.heap[1]

    def remove(self, value):
        self.heap = [val for val in self.heap if val != value]
        self._sinkDown(0)

    def _sinkDown(self, index):
        left = 2 * index + 1
        right = 2 * index + 2
        smallest = index

        if left < len(self.heap) and self.heap[left] < self.heap[smallest]:
            smallest = left

        if right < len(self.heap) and self.heap[right] < self.heap[smallest]:
            smallest = right

        if smallest != index:
            self.heap[index], self.heap[smallest] = self.heap[smallest], self.heap[index]
            self._sinkDown(smallest)

## Implementation Example - Real-time Stock Price Analysis 🎯

Here's a simple example of how we can use the Sliding Window Median to find the median stock price over a sliding window of 5 days.

```python
median_data = MinHeap()

# Inserting stock prices
median_data.insert(10)
median_data.insert(8)
median_data.insert(12)
median_data.insert(15)
median_data.insert(11)

# Removing the first day's data
median_data.remove(8)

# Printing the median
print(median_data.getMedian())  # Output: 10.0

Quiz 📝

In the next lesson, we'll delve deeper into the Sliding Window Median, discussing optimizations and advanced implementation scenarios. Stay tuned! 🎯