힙의 강력함에 대해

힙

힙은 여타 자료구조와 다른 부분이 많은 특이한 녀석이다. 힙의 특징들은 때에 따라 강력하게 작용할 수 있는데, 그러한 부분을 정리해보았다.

힙의 특징

• 최상위 노드인 루트가 힙의 최대 or 최소 -> O(1)의 시간복잡도로 최대/최소값 찾아내기 가능

• 추가적인 노드의 삽입, 삭제를 O(logN)으로 빠르게 수행 가능

• 메모리를 적게 먹는다.

그렇다면 힙을 어떻게 사용해야 좋을까?

• 동적인 입력에 대한 효율적인 처리가 필요할 때

• 빠른 정렬이 필요할 때 -> 힙 정렬

• 효율적인 우선순위 큐를 구현 가능

• 정렬되지 않은 데이터 중 중간값을 빠르게 찾아내야 할 때 -> 두개의 힙 이용

• etc) 중복된 요소 찾기, 최단 경로 찾기, 가까운 이웃 찾기 등..

직접 사용해보자

• 백준 1655번 가운데를 말해요

import sys
import heapq

N = int(sys.stdin.readline())

minHeap = []
maxHeap = []

def checkHeapDifer(min, max):
    if len(max) - len(min) == 0 or len(max) - len(min) == 1:
        pass
    else:
        if len(max) > len(min):
            heapq.heappush(min, -heapq.heappop(max))
        elif len(max) < len(min):
            heapq.heappush(max, -heapq.heappop(min))

        


for i in range(N):
    num = int(sys.stdin.readline())
    if i == 0:
        heapq.heappush(maxHeap, -num)
        print(num)
    else:
        if -maxHeap[0] == num:
            heapq.heappush(maxHeap, -num)
            checkHeapDifer(minHeap, maxHeap)
            print(num)
        elif -maxHeap[0] < num:
            heapq.heappush(minHeap, num)
            checkHeapDifer(minHeap, maxHeap)
            print(-maxHeap[0])
        elif -maxHeap[0] > num:
            heapq.heappush(maxHeap, -num)
            checkHeapDifer(minHeap, maxHeap)
            print(-maxHeap[0])

• 이와 같이 큰 데이터에서 중간값을 계속하여 구해야 할 경우 유용하게 사용 가능 (해당 문제는 이 외의 방법을 사용한다면 시간복잡도에서 걸리는 듯 하다.)

• 내가 작성한 코드에서는 최대 힙의 루트가 중간값이고, 최소 힙의 루트에서 찾아내는 방법도 있다. 이 경우는 두 힙의 역할이 반대가 되는데, 최대 힙의 루트값에서 찾아내는 방법이 훨씬 직관적이라 이를 사용했다.

• 또한 파이썬의 heapq 모듈을 통해 힙을 간편하게 다룰 수 있었다.
  이에 대한 내용은 전에 포스팅했으니 참고.

  https://velog.io/@dlgudwns1207/%ED%8C%8C%EC%9D%B4%EC%8D%AC%EC%9D%98-heapq-%EB%AA%A8%EB%93%88