<jupyter_start><jupyter_text>Problem 1The goal of this problem is to implement the "Median Maintenance" algorithm (covered in the Week 3 lecture on heap applications).  The text file contains a list of the integers from 1 to 10000 in unsorted order; you should treat this as a stream of numbers, arriving one by one.  Letting $x_i$ denote the $i^{th}$ number of the file, the $k{th}$ median $m_k$ is defined as the median of the numbers $x_1,\ldots,x_k$.  (So, if $k$ is odd, then $m_k$ is $((k+1)/2)^{th}$ smallest number among $x_1,\ldots,x_k$ ; if $k$ is even, then $m_k$ is the $(k/2)^{th}$ smallest number among $x_1,\ldots,x_k$.)In the box below you should type the sum of these 10000 medians, modulo 10000 (i.e., only the last 4 digits).  That is, you should compute $(m_1+m_2+m_3 + \cdots + m_{10000}) \bmod 10000$. OPTIONAL EXERCISE: Compare the performance achieved by heap-based and search-tree-based implementations of the algorithm.<jupyter_code>values = ProblemLoader(
    data_urls['problem1'], 
    fname="stream.p", 
    preprocessor=process_array
).fetch()
print(values[:10])
import heapq
import numpy as np

class MedianHeap():
    def __init__(self):
        self.median = np.inf
        self.minh = []
        self.maxh = []
        heapq.heapify(self.minh)
        heapq._heapify_max(self.maxh)

    def push(self, value):
        # If the new integer value is less than the current median, we put it in to the max-heap
        if value < self.median:
            self.maxh.append(value)
            heapq._heapify_max(self.maxh)
        else:
            heapq.heappush(self.minh, value)
        
        # if the size difference between two heaps are more than one take the top one out of the large heap and put it to the other.
        if abs(len(self.minh) - len(self.maxh)) > 1:
            if len(self.minh) > len(self.maxh): # min has more elements
                x = heapq.heappop(self.minh)
                self.maxh.append(x)
                heapq._heapify_max(self.maxh)
            else: # max has more elements
                x = heapq._heappop_max(self.maxh)
                heapq.heappush(self.minh, x)

        self.update_median()
        
    @private
    def update_median(self):
        if len(self.minh) == len(self.maxh):
            self.median = self.maxh[0] 
        else:
            if len(self.minh) > len(self.maxh):
                self.median = self.minh[0]
            else: 
                self.median = self.maxh[0]
        

h = MedianHeap()
m = []
for v in values:
    h.push(v)
    m.append(h.median)

print(len(h.minh), len(h.maxh))
print(len(m)) 
obfuscate(sum(m)) 
obfuscate(sum(m) % len(m))<jupyter_output>5000 5000
10000
{'fraction_non_alphanumeric': 0.11276516561220692, 'fraction_numerical': 0.021585411239300335, 'mean_word_length': 2.5091383812010446, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '187392', 'license': 'MIT', 'n_tokens_mistral': 953, 'n_tokens_neox': 884, 'n_words': 279, 'path': 'week3/heap.ipynb', 'repo_name': 'robbiemu/Graph-Search-Shortest-Paths-Data-Structures', 'size': '2687'}