힙 큐(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 함수를 사용하면 힙의 첫 번째 위치(인덱스 0), 즉 가장 작은 요소를 제거할 수 있습니다. 아래 예제에서는 힙에서 최솟값이 제거된 후 나머지 요소들이 힙 규칙에 맞게 재배열됩니다.
예제
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 함수는 항상 힙에서 가장 작은 요소를 제거한 뒤, 새로 들어온 요소를 고정된 순서 없이 적절한 위치에 삽입합니다. 삭제와 삽입이 한 번의 연산으로 동시에 처리되므로, heappop 후 heappush를 차례로 호출하는 것보다 효율적입니다.
예제
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]