[DSA][Heap] 07. Find Median from Data Stream

LeetCode 295

 

07. Find Median from Data Stream

The median is the middle value in an ordered integer list.
If the size of the list is even, there is no middle value, and the median is the mean of the two middle values.

For example, for arr = [2,3,4], the median is 3.
For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.
Implement the MedianFinder class:
- MedianFinder() initializes the MedianFinder object.
- void addNum(int num) adds the integer num from the data stream to the data structure.
- double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

 

 

[아이디어]

- minHeap에는 큰 원소들을 오름차순으로 저장하고, maxHeap에는 작은 원소들을 내림차순으로 저장하여 데이터를 두 부분으로 균등하게 관리하자.

 

 

[풀이 1] Min Heap & Max Heap

class MedianFinder:
    def __init__(self):
        self.largeDescHeap = []
        self.smallAscHeap = []

    def addNum(self, num: int) -> None:
        if self.largeDescHeap and self.largeDescHeap[0] > num:
            heapq.heappush(self.smallAscHeap, -num)
        else:
            heapq.heappush(self.largeDescHeap, num)
            
        if len(self.largeDescHeap) < len(self.smallAscHeap):
            heapq.heappush(self.largeDescHeap, -heapq.heappop(self.smallAscHeap))
        elif len(self.largeDescHeap) > len(self.smallAscHeap) + 1:
            heapq.heappush(self.smallAscHeap, -heapq.heappop(self.largeDescHeap))

    def findMedian(self) -> float:
        if len(self.largeDescHeap) != len(self.smallAscHeap):
            return self.largeDescHeap[0]
        else:
            return (self.largeDescHeap[0] - self.smallAscHeap[0]) / 2

실시간으로 데이터가 들어올 때, 전체 데이터를 두 개의 그룹으로 나누어 관리하면 중앙값(median)을 효율적으로 구할 수 있다.

이때, 데이터를 아래 절반 (작은 값들의 집합)과 위 절반 (큰 값들의 집합)으로 나누면 중앙값은 이 두 집합의 경계에 위치하게 되므로, 두 집합의 경곗값을 빠르게 알 수 있어야 하는데

• 아래 절반에서는 가장 큰 값을 빠르게 찾아야 하므로, 최대 힙(Max Heap)을 사용해 작은 값들 중 가장 큰 값을 관리한다.
• 위 절반에서는 가장 작은 값을 빠르게 찾아야 하므로, 최소 힙(Min Heap)을 사용해 큰 값들 중 가장 작은 값을 관리한다.

또한, 중앙값을 쉽게 구하려면 두 힙의 크기 차이가 1 이하가 되어야 하므로 두 힙의 크기를 같거나, 하나의 힙이 다른 힙보다 원소가 딱 한 개 더 많은 상태를 유지해야 한다.이렇게 하면, 데이터 개수가 홀수일 때는 더 큰 쪽 힙의 최상단 값이 중앙값이 되고, 데이터 개수가 짝수일 때는 두 힙의 최상단 값을 평균 내면 중앙값이 된다.

 

 

⏱️ 시간복잡도

addNum() : 새로운 숫자를 두 개의 힙 중 하나에 삽입하고, 균형을 맞추기 위해 힙에서 원소를 꺼내거나 넣는 연산을 수행한다. 힙 연산인 heappush와 heappop은 각각 O(log n) 이므로, addNum()의 시간 복잡도는 O(log n) 이다.

findMedian() : 두 힙의 최상단 원소를 바로 조회하거나 두 값을 평균 내는 작업만 수행하므로, 시간 복잡도는 O(1)이다.

🧠 공간복잡도

전체 데이터를 두 개의 힙에 나누어 저장하기 때문에, 저장 공간은 입력 데이터 크기에 비례한다. 따라서 공간 복잡도는 O(n)이다.