heapq 모듈은 최소 힙(min heap)을 구현하는 데 사용되며, 최소 힙은 가장 작은 요소가 루트에 위치함을 보장한다. 그러나 다른 요소들 사이의 상대적인 순서는 보장되지 않는다.
heapq의 각 원소의 인덱스를 k라고 할 때, k의 자식 원소들은 이진 트리 상의 특정 노드의 자식이 되므로 2k+1, 2k+2의 인덱스를 갖는다.
heapq는 부모 노드가 항상 자식 노드보다 그 값이 같거나 작다는 특징을 갖는다.
import 방법
import heapq
사용
heapq.heapify
heapq.heapify 함수는 기존의 자료구조를 힙으로 변환하는 함수다. 이 함수는 파라미터로 전달된 리스트의 원소들을 재배치하여 힙의 조건을 만족하도록 한다.
import heapq
print()
nums = [-5, 4, 1, 10, -9]
print(f'before heapq.heapify: {nums}')
heapq.heapify(nums)
print(f'after heapq.heapify: {nums}')
print()
# before heapq.heapify: [-5, 4, 1, 10, -9]
# after heapq.heapify: [-9, -5, 1, 10, 4]
heap.heapify의 시간 복잡도는 O(n)이다. 이는 리스트의 길이에 선형적으로 비례한다. 따라서, 리스트의 크기에 따라 선형적으로 작업 시간이 증가한다.
주의할 점은 heapq.heapify 함수를 사용하면 기존의 리스트가 변경된다는 것이다. 따라서, 원본 리스트를 보존해야 하는 경우에는 원본 리스트의 복사본을 만들어 작업하는 것이 좋다.
import heapq
print()
nums = [-5, 4, 1, 10, -9]
heap = nums[:]
print(f'nums before heapq.heapify: {nums}')
print(f'heap before heapq.heapify: {heap}')
heapq.heapify(heap)
print(f'nums after heapq.heapify: {nums}')
print(f'heap after heapq.heapify: {heap}')
print()
# nums before heapq.heapify: [-5, 4, 1, 10, -9]
# heap before heapq.heapify: [-5, 4, 1, 10, -9]
# nums after heapq.heapify: [-5, 4, 1, 10, -9]
# heap after heapq.heapify: [-9, -5, 1, 10, 4]
heapq.heappush
파이썬에서는 자료구조가 heapq에 의해 곧바로 heap으로 변환된다. heapq.heappush 메서드는 list와 같은 자료구조에 값을 추가하고, 추가된 값이 힙의 특성을 유지하도록 조정한다. 따라서, heappush를 사용하여 값을 자료구조에 추가하면 자료구조 자체가 힙으로 변환된다.
heappush 함수는 두 개의 인수를 받는다. 첫 번째 인수는 heap이라는 리스트(또는 heap이라고 부르는 다른 시퀀스)이고, 두 번째 인수는 heap에 추가할 요소다.
import heapq
print()
nums = []
print(f'before heapq.heappush: {nums}')
heapq.heappush(nums, 1)
heapq.heappush(nums, 4)
heapq.heappush(nums, -5)
heapq.heappush(nums, 10)
print(f'after heapq.heappush: {nums}')
print()
# before heapq.heappush: []
# after heapq.heappush: [-5, 4, 1, 10]
heappush를 사용하여 heap에 요소를 추가할 때, heapq 모듈은 새로운 요소를 적절한 위치에 삽입하여 최소 힙의 특성을 유지한다. 따라서, heap의 루트에는 항상 최소값이 있지만, 루트 외의 다른 노드들 간의 상대적인 순서는 보장되지 않는다.
heappush 메서드는 힙의 크기에 따라 푸시 작업이 필요한 조정 작업의 수가 증가하기 때문에 시간 복잡도는 O(logn)이다.
같은 타입의 값만 허용
heapq 모듈은 숫자를 기반으로 최소 힙을 구현하는 것을 목적으로 하고 있다. 따라서, 기본적으로 heapq에는 숫자가 들어간다. 숫자 타입의 값이 있는 상태에서 다른 타입의 값들(튜플, 문자열, 리스트 등)을 heapq에 추가하려고 시도하면 TypeError가 발생한다. 이는 해당 타입과 int 타입 간의 비교 연산이 불가능하기 때문이다.
import heapq
print()
nums = []
print(f'before heapq.heappush: {nums}')
heapq.heappush(nums, 1)
heapq.heappush(nums, 4)
**heapq.heappush(nums, (1, 2)) # 튜플
# TypeError: '<' not supported between instances of 'tuple' and 'int'
heapq.heappush(nums, 'a') # 문자열
# TypeError: '<' not supported between instances of 'str' and 'int'
heapq.heappush(nums, [-100, 100, 2]) # 리스트
# TypeError: '<' not supported between instances of 'list' and 'int'**
heapq.heappush(nums, -5)
print(f'after heapq.heappush: {nums}')
print()
그러나, 모든 인자를 동일한 타입으로 채운다면(dict를 제외한 list, tuple, float, str 등) heapq를 사용하여 정렬할 수 있다. 아래의 코드를 참고한다.
import heapq
print()
nums = []
print(f'before heapq.heappush: {nums}')
heapq.heappush(nums, (3, 2))
heapq.heappush(nums, (1, 2))
heapq.heappush(nums, (1, -2))
heapq.heappush(nums, (11, 2))
# heapq.heappush(nums, [3, 2])
# heapq.heappush(nums, [1, 2])
# heapq.heappush(nums, [1, -2])
# heapq.heappush(nums, [11, 2])
# heapq.heappush(nums, 'a')
# heapq.heappush(nums, 'b')
# heapq.heappush(nums, 'c')
# heapq.heappush(nums, 'd')
print(f'after heapq.heappush: {nums}')
print()
# before heapq.heappush: []
# after heapq.heappush: [(1, -2), (3, 2), (1, 2), (11, 2)]
값 조회
이렇게 만든 heap 자료구조에서 값을 조회하는 것은 list에서 값을 조회하는 것과 같다. 또한, heapq 모듈을 사용하여 구성된 힙은 최소 힙이기 때문에 인덱스 0에 있는 값이 항상 최소값이다. 따라서, nums[0]을 조회하면 힙에서 최소값을 얻을 수 있다.
import heapq
print()
nums = []
print(f'before heapq.heappush: {nums}')
heapq.heappush(nums, 1)
heapq.heappush(nums, 4)
heapq.heappush(nums, -5)
heapq.heappush(nums, 10)
print(f'after heapq.heappush: {nums}')
print(f'value 0: {nums[0]}')
print(f'value 1: {nums[1]}')
print(f'value 2: {nums[2]}')
print(f'value 3: {nums[3]}')
print()
# before heapq.heappush: []
# after heapq.heappush: [-5, 4, 1, 10]
# value 0: -5
# value 1: 4
# value 2: 1
# value 3: 10
그러나 위의 결과와 같이 인덱스 0는 heap에서 최소의 값임이 보장되지만, 인덱스 1, 2, 3 등 다른 인덱스에 있는 값들은 힙에서의 상대적인 순서를 나타내지 않는다. 즉, 인덱스 1에 있는 값이 두 번째로 작은 값이라는 보장이 없다. 힙은 부분적으로 정렬되어 있으며, 해당 노드의 자식 노드들과의 순서 관계만을 보장한다. 최소 힙에서 정렬된 순서로 값에 접근하기 위해서는 힙에서 값을 하나씩 추출해야 한다.
heapq.heappop
heapq.heappop은 heap 자료구조에서 값을 제거하는 메서드다. 이 메서드를 사용하면 자동으로 가장 작은 값을 제거하게 된다.
heappop을 사용하려면, heapq.heappop() 메서드의 인자로 대상이 되는 heap 자료구조를 넣는다.
import heapq
print()
nums = []
print(f'before heapq.heappush: {nums}')
heapq.heappush(nums, 1)
heapq.heappush(nums, 4)
heapq.heappush(nums, -5)
heapq.heappush(nums, 10)
print(f'after heapq.heappush: {nums}')
print(f'removed value: {heapq.heappop(nums)}')
print(f'after heapq.heappop: {nums}')
print()
# before heapq.heappush: []
# after heapq.heappush: [-5, 4, 1, 10]
# removed value: -5
# after heapq.heappop: [1, 4, 10]
heap에서 요소를 하나씩 꺼내어 출력하면 최소값부터 나오지만, 전체적으로 정렬된 상태로 요소가 저장되어 있는 것은 아니다. 만약 정렬된 순서로 요소를 얻고 싶다면, heappop 함수를 사용하여 heap에서 요소를 일일이 하나씩 꺼내어 사용해야 한다.
heapq.heappop의 시간 복잡도는 O(logn)이다. 이는 heap에서 최솟값을 제거하고 다시 힙 속성을 유지하는 연산이 수행되기 때문이다.
최대 힙
import heapq
print()
nums = [1, 4, -5, 2, 10]
heap = []
for num in nums:
heapq.heappush(heap, (-num, num))
while heap:
# print(f'heapq.heappop(heap): {heapq.heappop(heap)}')
print(f'heapq.heappop(heap)[1]: {heapq.heappop(heap)[1]}')
print(f'nums: {nums}')
print(f'heap: {heap}')
print()
# heapq.heappop(heap)[1]: 10
# heapq.heappop(heap)[1]: 4
# heapq.heappop(heap)[1]: 2
# heapq.heappop(heap)[1]: 1
# heapq.heappop(heap)[1]: -5
# nums: [1, 4, -5, 2, 10]
# heap: []
주어진 코드는 최대 힙을 구현하기 위해 음수 값을 사용한다. 코드에서 heapq.heappush(heap, (-num, num))은 heap에 원소를 추가하는 부분이다. 음수 값을 사용하여 원소를 추가함으로써, 내림차순으로 정렬된 최대 힙이 구성된다. 그 후 heapq.heappop(heap)[1]을 사용하여 힙에서 원소를 꺼내고, 결과를 출력한다. heapq.heappop을 호출할 때 [1]을 사용하여 두 번째 원소를 가져온 이유는 이 코드에서 원래 값인 양수 값을 출력하기 위해서다.
아래 코드를 참고한다.
import heapq
print()
nums = [1, 4, -5, 2, 10]
heap = []
for num in nums:
heapq.heappush(heap, (-num, num))
while heap:
print(f'heapq.heappop(heap): {heapq.heappop(heap)}')
# print(f'heapq.heappop(heap)[1]: {heapq.heappop(heap)[1]}')
print(f'nums: {nums}')
print(f'heap: {heap}')
print()
# heapq.heappop(heap): (-10, 10)
# heapq.heappop(heap): (-4, 4)
# heapq.heappop(heap): (-2, 2)
# heapq.heappop(heap): (-1, 1)
# heapq.heappop(heap): (5, -5)
# nums: [1, 4, -5, 2, 10]
# heap: []
최소 힙은 작은 값이 우선순위를 가지므로, 원래 숫자의 음수 값을 사용하여 가장 큰 값을 최소 힙에 추가한다. 그리고 num은 해당 숫자 그 자체를 나타낸다.
따라서, heapq.heappush(heap, (-num, num))는 heap에 (-num, num) 튜플을 추가하는 것이다. (-num, num) 튜플은 원래 숫자의 음수와 해당 숫자 그 자체로 구성되어 있다. 이를 통해 최소 힙에서는 음수 값이 가장 큰 값으로 취급되며, heap에 추가될 때 우선순위를 가지게 된다.