[알고리즘] 힙(Heap) 자료구조

이것이 취업을 위한 코딩 테스트다. with 파이썬 책을 참고하여 정리한 내용입니다.

✅ 힙(Heap) 자료구조

힙 자료구조는 우선순위 큐(Priority Queue)를 구현하기 위하여 사용하는 자료구조 중 하나이다. 우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제한다는 점이 특징이다.

스택, 큐, 우선순위 큐 자료구조 비교

자료구조	추출되는 데이터
스택(Stack)	가장 나중에 삽입된 데이터
큐(Queue)	가장 먼저 삽입된 데이터
우선순위 큐(Priority Queue)	가장 우선순위가 높은 데이터

✅ 힙 자료구조 시간 복잡도

데이터의 개수가 N개일 때, 삽입 시간과 삭제 시간은 모두 $O(logN)$으로 각각 N번 반복하므로 삽입과 삭제를 모두 진행하면 $O(2NlogN)$이 되는데, 빅오 표기법에 따라 전체 시간 복잡도는 $O(NlogN)$이 된다. 이는 힙 정렬(Heap Sort)의 원리를 이용한 것이다.

✅ heapq 라이브러리

파이썬에서는 우선순위 큐 라이브러리로 PriorityQueue 혹은 heapq를 지원하는데, 일반적으로 heapq가 더 빠르게 동작하기 때문에 heapq를 사용하자.

heapq라이브러리는 기본적으로 최소 힙 구조를 이용한다. 최소 힙구조는 ‘값이 낮은 데이터가 먼저 삭제’된다. 최대 힙은 ‘값이 큰 데이터가 먼저 삭제’되는데, 최대 힙을 구현하기 위해 일부러 우선순위에 해당하는 값에 음수 부호(-)를 붙여 넣었다가, 나중에 꺼낸 다음 음수 부호(-)를 붙여서 원래의 값으로 돌리는 방식을 사용한다.

✅ heapq 라이브러리 사용법

✔️ 라이브러리 임포트

파이썬 내장 라이브러리이므로 파이썬만 설치되어 있으면 불러올 수 있다.

import heapq
from heapq import heappush, heappop ...

✔️ 힙 생성

heapq 라이브러리에서는 파이썬의 리스트를 최소 힙처럼 다룰 수 있도록 해준다. 그래서 빈 리스트를 생성하면 된다.

heap = []

✔️ 원소 추가

heapq 라이브러리리의 heappush() 함수를 이용한다. 첫 번째 인자는 원소를 추가할 대상 리스트이며, 두 번째 인자는 추가할 원소이다.

import heapq

heap = []

heapq.heappush(heap, 7)
heapq.heappush(heap, 2)
heapq.heappush(heap, 8)
heapq.heappush(heap, 3)

print(heap)

[2, 3, 8, 7]

✔️ 원소 삭제

heapq 라이브러리리의 heappop() 함수를 이용한다. 원소를 삭제할 대상 리스트를 인자로 넘기면 가장 작은 원소를 리턴하며 삭제합니다.

print(heapq.heappop(heap))
print(heap)

2
[3, 7, 8]

✔️ 기존 리스트를 힙으로 변환

이미 원소가 들어있는 리스트를 힙으로 만드려면 heapq 라이브러리의 heapify() 함수를 사용하면 된다. 새로운 리스트를 반환하는 것이 아닌 기존 리스트를 변환하므로, 원본 리스트를 유지해야 한다면 반드시 복제 후 변환을 해야한다.

heap = [7, 2, 8, 3]
heapq.heapify(heap)
print(heap)

[2, 3, 8, 7]

✔️ 최대 힙으로의 응용

앞서 말한대로 최소 힙 구조인 heapq를 최대 힙으로 사용하려면 우선순위 값에 음수 부호(-)를 붙여주면 된다.

import heapq

nums = [7, 2, 8, 3]
heap = []

for n in nums:
    heapq.heappush(heap, (-n, n))

while heap:
    print(heapq.heappop(heap)[1], end=' ')

8 7 3 2