8️⃣

힙 (Heap - priority queue)

강의 만들 때 참고할 것들

우리가 전에 배운 queue는 First in-First Out 구조였습니다.

즉 아래와 같은 queue가 있을 때 , popleft를 하면 5→3→9

\cdots

→6 순으로 요소들이 나올 것입니다.

하지만 이때 들어온 순서에 상관없이, 일정한 기준(우선 순위)에 따라 요소들이 나오도록 할 수 있는데, 이를 일반적인 queue와 구별하여 , priority queue라고 합니다.

예를 들어 작은 순서대로 원소들을 출력하고 싶을 때는 어떻게 해야할까요? naive하게 생각해보면, 아래와 같이 코드를 짤 수 있을 것입니다.

queue.remove(min(queue))
Python
복사

그러나 이렇게 할 시

O(N)

의 시간 복잡도를 가집니다. min() 함수에서 가장 작은 원소를 찾는데

O(N)

이 걸리고, 또 remove()에서

O(N)

이 걸려서 총

O(2N) = O(N)

의 시간복잡도가 걸립니다.

혹자는 이렇게 생각할 수도 있을 것입니다. 처음에 오름차순으로 정렬하고, 젤 앞에 있는 원소를 꺼내면 되는 것 아닌가? 그럼 O(nlog(n))의 시간 복잡도를 가질 것이고…

queue = sorted(deque([5, 3, 9, 4, 1, 2, 6]))
Python
복사

이렇게 하면 확실히, 시간복잡도 측면에서, 이득을 볼 수 있습니다.

하지만, 새로운 원소들을 추가하는 경우에 있어, 정렬을 일일이 해줘야 한다는 단점이 존재합니다.

원소를 추가할 때마다, 오름차순으로 알아서 정렬해주는 자료구조가 있으면 편하지 않을까요? heap이라는 자료구조를 통해 priority queue를 구현할 수 있습니다.

heap

코딩 테스트에서는 heap을 일일이 구현할 필요가 없으며, 이미 잘 만들어진 heap을 잘 활용하는 것이 중요합니다. 그렇기에 heap의 활용 과정을 먼저 보고, 시간복잡도를 살펴보도록 합시다.

heapq

heap과 관련된 모듈은 파이썬에서 heapq로 구현 되었습니다.

from heapq import heapify, heappop, heappush
Python
복사

heap의 선언

heap의 선언은 상당히 간단합니다. 비어있는 heap에서 시작하고 싶으면, 단순히 list를 선언하는 것과 같이 하면 됩니다.

Python
복사

이미 존재하는 리스트를 heap으로 만들고 싶으면 heapify를 사용합니다.

a = [3, 5, 2, 1, 6, 4]
heapify(a)
Python
복사

heap의 원소 추가

heap의 0 원소를 추가해보도록 합시다. heappush()함수에 heap과 원소를 차례대로 넣어주면 됩니다.

heappush(a, 0)
Python
복사

heap의 원소 삭제

heappop()을 사용하면, 제일 작은 원소가 pop됩니다.

Python
복사

heap의 정의

heap은 min heap과 max heap으로 나누어져 있습니다. 각각의 정의는 아래와 같습니다.

•

min heap: 자식 노드의 값이 부모 노드의 값보다 큰 트리 형태의 자료구조

•

max heap: 자식 노드의 값이 부모 노드의 값보다 작은 트리 형태의 자료 구조

다음과 같이 list가 있을 때, heapify를 사용하면, min heap 또는 max heap으로 만들 수 있습니다.

min heap

max heap

트리가 아니라 트리 형태의 자료 구조 인것은, 힙을 구현하는데에 있어 array를 사용하기 때문입니다. 즉, 자식 노드들을 node.left, node.right로 표현하는 것이 아니라, array의 index를 활용합니다. 부모노드가 i index라고 하면, 왼쪽 자식노드는 2i+1 index에, 오른쪽 자식노드는 2i+2 index에 위치합니다.

즉, 트리 형태의 heap은 아래의 array로 표현 되는 것입니다.

Python
복사

min heap으로 만들었을 때, a[0]은 항상 제일 작은 값이지만, 그 이후로 부터는 알 수 없습니다. 즉 a[1]이 두 번째로 작은 것을 보장할 수 없습니다. 왜냐면, heap에서 왼쪽 자식노드와 오른쪽 자식 노드의 크기를 비교하지 않기 때문입니다. 그래서 위의 예시에서도 1,3,2,... 순으로 정렬된 것을 확인할 수 있습니다.

max heap도 마찬가지입니다. 다만 파이썬에서 max heap이 따로 구현 되어 있지 않기에, 약간의 꼼수를 써야 합니다.

위와 같이 array로 표현하려면 어떻게 해야할까요? heapify는 [1,3,2,4,5,9,6] 로 만들기에 적절치 않아 보입니다.

첫 번째 방법은 각 원소에 -1을 곱해주는 것입니다.

이렇게 할 시 heapify를 사용하게 되면, 아래와 같이 heap으로 만들어 줄 것입니다.

그리고 heappop을 할 때, 다시 -1을 곱하여 출력해주면 [9,4,6,3,1,2,5]의 순으로 출력이 될 것입니다.

value = -1 * heappop(a)
Python
복사

list를 활용하기

기본적인 발상은 위와 똑같습니다. 이런 식으로 이중 리스트를 만들면, 그 후 heapify는 다음과 같이 heap을 만듭니다.

1번과 비슷한 방식으로 다시 원래 값들을 접근할 수 있습니다.

weight , value = heappop(a) 
Python
복사

value = heappop(a)[1]
Python
복사

heap의 시간복잡도


heapify()	$O(n)$
heappush()	$O(\log n)$
heappop()	$O(\log n)$