Heap

Question 1

Implement

Median Data Structure Using Heaps With 2 Methods: insert_num(num), find_median()

Answer 1

from heapq import *

class MedianOfStream:
  def \_\_init\_\_(self):
    self.lt_med_max_heap = []
    self.gte_med_min_heap = []
    return

  def insert_num(self, num):
    if not self.lt_med_max_heap and not self.gte_med_min_heap:
      heappush(self.lt_med_max_heap, -num)
      return
    
    median = self.find_median()
    if num > median:
      heappush(self.gte_med_min_heap, num)
    else:
      heappush(self.lt_med_max_heap, -num)
      
    if len(self.gte_med_min_heap) > len(self.lt_med_max_heap):
      heappush(self.lt_med_max_heap, -heappop(self.gte_med_min_heap))
    elif len(self.lt_med_max_heap) - len(self.gte_med_min_heap) > 1:
      heappush(self.gte_med_min_heap, -heappop(self.lt_med_max_heap))
    
    return
    
  def find_median(self):
    if len(self.lt_med_max_heap) != len(self.gte_med_min_heap):
      return -self.lt_med_max_heap[0]
    else:
      return (-self.lt_med_max_heap[0] + self.gte_med_min_heap[0]) / 2

Question 2

Implement

Min Heap Class with methods: push(val), pop(), peek(). Add support so that the native len() function works

Answer 2

class MinHeap:
    def \_\_init\_\_(self):
        self.heap = []

    def push(self, val):
        self.heap.append(val)
        self._sift_up(len(self.heap) - 1)

    def _sift_up(self, i):
        parent = (i - 1) // 2
        while i > 0 and self.heap[i] < self.heap[parent]:
            self._swap(i, parent)
            i = parent
            parent = (i - 1) // 2

    def pop(self):
        if not self.heap:
            return None
        self._swap(0, len(self.heap) - 1)
        min_val = self.heap.pop()
        self._sift_down(0)
        return min_val

    def _sift_down(self, i):
        left = 2 * i + 1
        right = 2 * i + 2
        smallest = i

        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 != i:
            self._swap(i, smallest)
            self._sift_down(smallest)        

    def peek(self):
        return self.heap[0] if self.heap else None

    def _swap(self, i, j):
        self.heap[i], self.heap[j] = self.heap[j], self.heap[i]

    def \_\_len\_\_(self):
        return len(self.heap)