이 글에서는 Python의 heapq 모듈을 사용해 두 개의 정렬된 리스트를 하나로 병합하는 방법을 살펴봅니다. 예를 들어 list1 = [10, 20, 30, 40]과 list2 = [100, 200, 300, 400, 500]을 병합하면 [10, 20, 30, 40, 100, 200, 300, 400, 500]처럼 전체가 정렬된 결과 리스트를 얻을 수 있습니다.
이 작업에는 heapq.merge() 함수가 가장 적합합니다. heapq 모듈은 파이썬에 기본으로 포함된 표준 라이브러리이므로, 별도의 설치 없이 임포트만 하면 바로 사용할 수 있습니다.
import heapq
heapq 모듈의 주요 메서드
heapq 모듈에서 자주 사용되는 메서드는 다음과 같습니다.
heapq.heapify(iterable)
반복 가능한(iterable) 데이터를 최소 힙(min-heap) 자료구조로 변환합니다.
heapq.heappush(heap, element)
힙에 새 요소를 삽입한 뒤, 힙 속성을 유지하도록 전체 구조를 재정렬합니다.
heapq.heappop(heap)
힙의 최상위(root)에 있는 가장 작은 요소를 반환하고 삭제한 후, 나머지 요소들로 힙을 재구성합니다.
heapq.heappushpop(heap, element)
요소를 삽입하는 동작과 추출(pop)하는 동작을 한 번의 호출로 처리합니다. 먼저 요소를 넣은 뒤 가장 작은 값을 꺼냅니다.
heapq.heapreplace(heap, element)
삽입과 추출을 한 문장으로 수행한다는 점은 heappushpop과 같지만, 실행 순서가 반대입니다. 즉, 먼저 힙의 루트 요소를 제거한 후 새 요소를 삽입합니다.
heapq.nlargest(n, iterable, key=None)
데이터 집합에서 가장 큰 n개의 요소를 반환합니다.
heapq.nsmallest(n, iterable, key=None)
데이터 집합에서 가장 작은 n개의 요소를 반환합니다.
병합 예제 코드
아래 예제에서는 정렬되지 않은 두 개의 리스트를 각각 정렬한 후, heapq.merge()로 병합합니다.
import heapq
first_list = [45, 12, 63, 95, 74, 21, 20, 15, 36]
second_list = [42, 13, 69, 54, 15]
first_list = sorted(first_list)
second_list = sorted(second_list)
print('첫 번째 정렬된 리스트: ' + str(first_list))
print('두 번째 정렬된 리스트: ' + str(second_list))
final_list = list(heapq.merge(first_list, second_list))
print('최종 병합 리스트: ' + str(final_list))
실행 결과
첫 번째 정렬된 리스트: [12, 15, 20, 21, 36, 45, 63, 74, 95]
두 번째 정렬된 리스트: [13, 15, 42, 54, 69]
최종 병합 리스트: [12, 13, 15, 15, 20, 21, 36, 42, 45, 54, 63, 69, 74, 95]
참고 사항
heapq.merge()는 입력으로 들어오는 이터러블이 이미 정렬되어 있다고 가정하고 동작합니다. 따라서 위 예제처럼 미리 sorted()로 정렬해 두어야 올바른 결과를 얻습니다. 이 함수는 단순히 두 리스트를 이어 붙인 뒤 정렬하는 것보다 효율적이며, 내부적으로 각 입력을 순차적으로 비교하므로 시간 복잡도는 O(N + M)에 가깝습니다. 또한 결과를 리스트로 만들지 않고 제너레이터 형태로 그대로 사용하면 대용량 데이터도 메모리를 절약하며 처리할 수 있습니다.