[Python] 파이썬 heap 자료구조, heapq 모듈 사용

힙은 최대값과 최소값을 빠르게 찾아주는 자료구조이며 완전 이진 트리를 기반으로 하고, 우선순위 큐 알고리즘이라고도 부릅니다. 

 

힙은 최대 힙과 최소 힙으로 나뉘는데 파이썬에서 제공하는 heapq는 최소 힙을 기본으로 합니다.

 

• 최소 힙 : 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙
• 최대 힙 : 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

 

heap의 데이터 삽입과 삭제는 O(logN)의 시간 복잡도를 보장합니다.

 

부모 노드와 자식 노드이 인덱스 관계는 다음과 같습니다.

 

1. 부모 노드 인덱스 = 자식 노드 인덱스 // 2

2. 왼쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2

3. 오른쪽 자식 노드 인덱스 = 부모 노드 인덱스 * 2 + 1

 

즉, 부모 노드 인덱스를 k라 하면 왼쪽 자식 노드 인덱스는 2k가 되고 오른쪽 자식 노드 인덱스는 2k+1가 됩니다.

 

heapq 모듈을 사용하기 위해선 다음과 같이 추가를 해주어야 합니다.

import heapq

 

1. 원소 추가

heapq.heappush(리스트, 추가할 요소) : 리스트에 추가할 요소를 넣음

 

import heapq
heap = []
heapq.heappush(heap, 12)
print(heap)

 

결과)

[12]

 

heap이라는 이름을 가진 리스트에 heapq.heappush를 사용해서 정수 12를 삽입했습니다.

 

import heapq
heap = [ 12 ]
heapq.heappush(heap, 7)
print(heap)

 

결과)

[7, 12]

 

정수 12가 들어있는 리스트에 heappush로 정수 7을 삽입하니 정렬이 된 모습입니다.

 

import heapq
heap = [ ]
heapq.heappush(heap, 7)
heapq.heappush(heap, 15)
heapq.heappush(heap, 9)
heapq.heappush(heap, 5)
heapq.heappush(heap, 17)
print(heap)

 

결과)

[5, 7, 9, 15, 17]

 

heap[0]은 가장 작은값으로 정렬이 됩니다.

 

2. 원소 삭제

heapq.heappop(리스트) : 리스트의 가장 작은 원소인 heap[0]을 삭제해줌

 

위의 결과로 나온 리스트 heap = [ 5, 7, 9, 15, 17 ]에서 heapq.heappop(heap)을 해보겠습니다.

heapq.heappop(heap)
print(heap)

 

결과)

[7, 15, 9, 17]

 

3. heap으로 변환

heapq.heapify(리스트)

 

import heapq
heap = [ 13, 8, 11, 19, 6 ]
heapq.heapify(heap)
print(heap)

 

결과)

[6, 8, 11, 19, 13]

 

heapq.heapify()를 통해 일반 리스트를 최소 힙을 유지하는 heap자료구조로 바꾸었습니다.

 

4. heapq를 이용한 최대 힙 구현

파이썬은 최소 힙만을 지원하기 때문에 최대 힙을 구현하기 위해서는 음수를 삽입하는 방법을 사용해야 합니다.

 

import heapq
elements = [ 13, 8, 11, 19, 6 ]
heap = []
for element in elements:
    heapq.heappush(heap, -element)
for i in range(len(heap)):
    print(-heapq.heappop(heap), end=' ')

 

결과)

19 13 11 8 6

 

heap에 elements의 요소를 음수 값으로 삽입해주고 heap내부에서 음수값을 가진채 최소 힙 정렬이 된 원소들은 출력될때 -1을 곱하고 출력하게 되어 최대 힙으로 출력할 수 있게 됩니다.