힙 (Heap)

 

 

1. Find Median from Data Stream 

문제 : https://leetcode.com/problems/find-median-from-data-stream

 

 

숫자가 더해지는 연산과 더해진 리스트이 중간값을 찾는 문제이다. 

리스트가 짝수인 경우에는 중간의 2자리를 더하고 결과를 Double로 반환한다.

 

이 문제는 단순 리스트로 문제를 풀려고하면 Time Limit Exceeded 예외가 발생한다 .

우선순위 큐를 이용해서 간단하게 중간값을 구할 수 있다. 

 

최소 우선순위 큐인 minHeap과 최대 우선순위 큐인 maxHeap을 사용하고 이 둘의 길이를 항상 반으로 유지하도록 해서 리스트를 반으로 쪼개 구성하는 방식이다. 

 

값을 더하는 addNum()의 경우 

시간복잡도는 O(logN) 

공간복잡도는 O(N) 

findMedian()의 경우 

값을 하나씩만 꺼내면 되므로 시간복잡도는 O(1)

공간복잡도는 O(1)

import java.util.Collections

class MedianFinder() {
    
    val maxHeap = PriorityQueue<Int>(Collections.reverseOrder())
    val minHeap = PriorityQueue<Int>()

    fun addNum(num: Int) {
        maxHeap.offer(num)
        minHeap.offer(maxHeap.poll())

        if(maxHeap.size<minHeap.size) {
            maxHeap.offer(minHeap.poll())
        }
    }

    fun findMedian(): Double {
        return if(maxHeap.size > minHeap.size) {
            maxHeap.peek().toDouble()
        } else {
            (maxHeap.peek() + minHeap.peek()) / 2.0
        }
    }

}