힙 큐(Heap Queue)는 각 부모 노드가 자식 노드보다 작거나 같은 값을 갖는 특수한 트리 구조입니다. 파이썬에서는 내장 모듈인 heapq를 통해 힙을 손쉽게 구현할 수 있으며, 처리 우선순위가 높은 항목을 먼저 꺼내야 하는 우선순위 큐(Priority Queue)를 만들 때 특히 유용합니다.
heapq 모듈의 주요 함수
파이썬의 내장 라이브러리인 heapq는 힙 자료구조에 대한 다양한 연산을 수행할 수 있는 함수들을 제공합니다. 주요 함수는 다음과 같습니다.
- heapify – 일반 리스트를 힙 구조로 변환합니다. 변환 결과 가장 작은 요소가 인덱스 0 위치로 이동하지만, 나머지 요소들이 반드시 정렬되는 것은 아닙니다.
- heappush – 기존 힙의 구조를 유지한 채 새로운 요소를 추가합니다.
- heappop – 힙에서 가장 작은 요소를 제거한 후 반환합니다.
- heapreplace – 힙에서 가장 작은 요소를 제거하고, 함수에 전달된 새로운 값으로 대체합니다.
힙 생성하기
힙은 요소가 담긴 리스트에 heapify 함수를 적용하는 것만으로 간단히 만들 수 있습니다. 아래 예제에서는 리스트를 전달하면 heapify 함수가 요소들을 재배열하여 가장 작은 값이 첫 번째 위치로 오도록 만듭니다.
예제
import heapq H = [21, 1, 45, 78, 3, 5] # heapify로 요소 재배열 heapq.heapify(H) print(H)
실행 결과
[1, 3, 5, 78, 21, 45]
힙에 요소 삽입하기
heappush 함수를 사용하면 힙에 새로운 요소를 추가할 수 있습니다. 새 요소는 우선 리스트의 마지막에 추가된 뒤, 힙 속성을 유지하도록 자동으로 적절한 위치로 이동합니다. 아래 예제에서는 숫자 8을 삽입합니다.
예제
import heapq H = [21, 1, 45, 78, 3, 5] # 리스트를 힙으로 변환 heapq.heapify(H) print(H) # 요소 추가 heapq.heappush(H, 8) print(H)
실행 결과
[1, 3, 5, 78, 21, 45] [1, 3, 5, 78, 21, 45, 8]
힙에서 요소 제거하기
heappop 함수를 사용하면 힙의 첫 번째 위치, 즉 가장 작은 값을 가진 요소를 제거하고 그 값을 반환합니다. 아래 예제에서는 힙에서 가장 작은 요소인 1이 제거됩니다.
예제
import heapq H = [21, 1, 45, 78, 3, 5] # 힙 생성 heapq.heapify(H) print(H) # 힙에서 요소 제거 heapq.heappop(H) print(H)
실행 결과
[1, 3, 5, 78, 21, 45] [3, 21, 5, 78, 45]
힙에서 요소 교체하기
heapreplace 함수는 힙에서 가장 작은 요소를 먼저 제거한 뒤, 새로 전달된 요소를 삽입합니다. 새 요소가 들어갈 위치는 고정되어 있지 않으며, 힙 속성을 유지하는 방향으로 배치됩니다.
예제
import heapq H = [21, 1, 45, 78, 3, 5] # 힙 생성 heapq.heapify(H) print(H) # 요소 교체 heapq.heapreplace(H, 6) print(H)
실행 결과
[1, 3, 5, 78, 21, 45] [3, 6, 5, 78, 21, 45]