힙 자료구조
파이썬에서 heapq 모듈은 이진트리(binary tree) 기반의 최소 힙(min heap) 자료구조를 제공하는 모듈이다.
여기서 힙(heap)이란 완전 이진 트리 자료구조(complete binary heap)의 일종으로
힙에는 두가지의 종류가 있다.
-
최소 힙(min heap): 루트 노드가 가장 작은 값을 가지며 따라서 값이 작은 데이터부터 우선적으로 제거된다.
-
최대 힙(max heap): 루트 노드가 가장 큰 값을 가지며 따라서 값이 큰 데이터부터 우선적으로 제거 된다.
또한 heapq 모듈은 완전 이진트리를 기반으로 하는데,
완전 이진 트리란 부모 노드(=k)로 부터 왼쪽 자식 노드(=2k+1)에서 오른쪽 자식 노드(=2k+2)순으로 데이터가 십입되는 트리를 말한다.
아래는 완전이진 트리 형태의 최소 힙 자료구조의 예시이다.
최소 힙의 새로운 요소 추가
최소 힙에서 새로운 요소가 추가 되었을때 최소 힙의 특성을 만족하는 방법은 다음과 같다.
새로운 요소 값인 1이 추가 되었다고 가정 했을때, 1은 자신의 부모노드의 값과 비교하여 값이 더 작을 경우 부모 노드 쪽으로 이동 하게 된다.
위의 예시에서 1인 부모 노드의 값이 5보다 작기 때문에 부모 노드쪽으로 이동하고 다시 부모 노드 값인 3과 비교하여 자신의 값인 1이 더 작기 때문에 루트 노드까지 이동하게 된다.
따라서 최소 힙의 특성을 만족하기 위해서 시간 복잡도 O(logN)의 시간 복잡도를 가진다.
최소 힙의 요소 제거
최소 힙의 특성을 만족하면서 요소를 제거하는 방법은 다음과 같다.
먼저 루트 노드가 제거되면 가장 마지막의 값인 5가 루트 노드로 이동하게 된다. 그 후 루트 노드는 자신의 왼쪽 자식 노드와 오른쪽 자식 노드를 비교하여 더 작은 자식 노드와 자리를 바꾼다.
요소 제거 후 확인해 보면 여전히 최소 힙의 특성이 유지되어 있는 것을 확인 할 수 있다.
파이썬에서는 이러한 이진트리를 기반으로 하는 최소 힙 자료구조를 구현하는 heapq 모듈을 제공한다.
아래는 heapq 모듈에서 제공하는 메서드이다.
여기서 매개변수 heap은 [ ]로 초기화된 리스트로 정의 하겠다.
heapq.heappush(heap, item)
heapq.heappush 메서드는 최소 힙 자료구조 특성을 유지한채 item의 값을 heap으로 추가한다.
numbers = [3, 8, 5, 9, 7]
result = []
for i in numbers:
heapq.heappush(result, i)
print(result) # [3, 7, 5, 9, 8]heapq 메서드로 요소 추가시 가장 작은 값이 index 0번에 위치 하게 되고 index 1번(=k)의 값인 7에 대하여 그 자식 노드인 index 3(=2k+1)의 값이 9로 부모 노드의 값이 더 작으므로 최소 힙의 특성을 만족하는 것을 확인 할 수 있다.
따라서 heappush 메서드는 최소 힙 자료구조 특성을 유지하므로 시간 복잡도 O(logN)의 시간 복잡도를 가진다.
heapq.heappop(heap)
heapq.heappop 메서드는 최소 힙 자료구조 특성을 유지한채 heap의 첫번째 요소을 삭제 후 반환한다.
이때 heap이 비어있다면 오류를 발생시킨다.
for _ in range(len(numbers)):
print(heapq.heappop(result)) # 3 5 7 8 9최소 힙은 루트 노드에 가장 작은 값을 위치 시키고 루트 노드의 값을 반환한다. 따라서 heappop 메서드의 실행 결과 오름차순 정렬되는 것을 확인 할 수 있다.
heapq.heappushpop(heap, item)
heapq.heappushpop 메서드는 최소 힙 자료구조 특성을 유지한채 item을 heap으로 푸시한 후 heap의 첫번째 요소를 삭제 후 반환한다.
heapq.heappush 메서드와 heapq.heappop를 한번에 수행 할 수 있는 메서드라고 생각하면 된다.
이때 heap이 비어있으면 오류를 발생시킨다.
heapq.heapify(x)
heapq.heapify 메서드는 기존에 존재하는 리스트 x를 매개변수로 받아 힙으로 변환하는 메서드이다.
numbers = [3, 8, 5, 9, 7]
heapq.heapify(numbers)
print(numbers) # [3, 7, 5, 9, 8]리스트의 요소를 하나하나 추가 하지 않아도 heapify 메서드는 리스트 자체를 최소 힙의 특성을 가지는 리스트로 만들어준다.
