[WEEK 2] 우선순위 큐

우선 순위 큐를 활용한 중간 값을 구하는 방식이 있어 저장해본다.

해당 방식은 최소힙과 최대힙을 활용하여 중간값을 구한다.

 

이러한 방식은 기본적인 탐색보다 빠른 시간 복잡도를 가진다. 전체 입력을 받은 뒤O(n log n)의 복잡도로 매우 빠르다.

# 우선 순위 큐에서 중간 값을 찾기 위해서는 최대 힙, 최소 힙 사용
# 최대 힙에는 중간값 이하의 값을, 최소 힙에는 중간값 초과의 값을 넣기
def add_num(num):
    if not max_heap or num <= -max_heap[0]:
        heapq.heappush(max_heap, -num)
    else:
        heapq.heappush(min_heap, num)
        
    if len(max_heap) < len(min_heap):
        heapq.heappush(max_heap, -heapq.heappop(min_heap))
    elif len(max_heap) > len(min_heap) +1:
        heapq.heappush(min_heap, -heapq.heappop(max_heap))