#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/heaps-priority-queues/median-stream-implementation

░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░███████████████████████████████████████████████████████████████████████████████████████████████

#####   ######  #####    ###    #   #  ###  #   #  ######
##  ##  ##      ##  ##  ## ##   #   #   #   #   #  ##
#####   ####    #####   #   #   #   #   #   #   #  ####
##  #   ##      ##      ## ##    # #    #    # #   ##
##   #  ######  ##       ###      #    ###    #    ######

$ curl repovive.com/roadmaps/data-structures/heaps-priority-queues/median-stream-implementation

Repovive

Median Stream - Implementation - Heaps & Priority Queues | Data Structures | Repovive

Repovive.

Data Structures19 sections · 729 units49h total

Open in Course

Median Stream - Implementation

Complete solution

Here's the solution:

class MedianFinder
    maxHeap := empty max-heap  // smaller half
    minHeap := empty min-heap  // larger half

    function addNum(num)
        insert num into maxHeap
        insert (extract max from maxHeap) into minHeap

        if size of minHeap > size of maxHeap
            insert (extract min from minHeap) into maxHeap

    function findMedian()
        if size of maxHeap > size of minHeap
            return root of maxHeap
        return (root of maxHeap + root of minHeap) / 2.0

Time: $O(\log n)$ per insertion, $O(1)$ for median. Space: $O(n)$ .