데이터를 정렬된 상태로 유지해주는 파이썬의 내부 모듈 heapq에 대해 알아보자!🧐
1. 개요
heapq 모듈은 이진 트리 기반의 최소 힙 자료구조를 제공한다.
예를 들어
[3,6,4,8,2,1]이 배열에서 가장 작은 정수를 구하기 위해서는 for문을 돌려 시간복잡도는 O(N)이 될 것이다.
하지만 힙은 logN의 속도로 더 빠르게 찾을 수 있게 도와준다.
그러니 먼저 힙 자료구조에 대해 알아보자
2. 힙 자료구조란?
- 완전 이진 트리의 일종으로 우선순위 큐를 위해 만들어졌다.
- 여러 개의 값 중에 최대값과 최솟값을 빠르게 찾을 수 있다.
- 힙 트리에서는 중복된 값도 허용한다 (이진 탐색 트리에서는 허용 X)
🔮 완전 이진 트리
마지막을 제외한 모든 노드에서 자식들이 꽉 채워진 이진트리
힙은 루트가 가장 작은 값인 최소힙과 루트가 가장 높은 값인 최대힙이 있다.
- 루트는 최소값인 1
- 자식은 자신보다 크기만 하면 되기때문에 왼쪽, 오른쪽 상관 없다.
- 왼쪽 자식은 부모 인덱스 * 2
- 오른쪽 자식은 부모 인덱스 * 2 + 1
push나 pop을 실행하면 자식 인덱스와 비교하면서 루트까지 오게 된다.
3. 👨💻 사용법
1. 모듈 설치
- 내장 모듈이기 때문에 설치 안해도 된다.
import heapq
heap = []2. 힙에 원소 추가(heappush)
heapq.heappush함수를 이용해
첫번째 인자에는 원소를 추가할 리스트
두번째 인자에는 추가할 원소를 적는다.
heapq.heappush(heap, item)
heapq.heappush(heap, item2)
print(heap)
# [item, item2]3. 힙에 있는 원소 삭제(heappop)
heap = [1, 2, 3, 4, 5]
heapq.heapppop(heap)
print(heap)
# [2, 3, 4, 5]- 변수를 pop과 같이 적으면 삭제하면서 결과를 확인할 수 있다.
4. 원래 있는 배열을 힙으로(heapify)
import heapq
arr = [3, 5, 2, 4]
heapq.heapify(arr)
print(arr)
# [2, 3, 4, 5]5. 최대 힙
- heapq에서는 최소 힙만 지원해준다.
- 그래서 키 값을 -로 바꿔주면 된다.
- 키 값을 바꾸는 시간은 O(N)이고 힙 요소를 얻는데는 O(nlog n)이라서 시간 복잡도에는 문제 되지 않는다.
reverse = lambda x: x * -1
max_heap = list(map(reverse, heap))
heapq.heapify(max_heap)
max_heap = list(map(reverse, max_heap))음수로 바꿨다가 다시 양수로 바꿔야되기 때문에 매우 번거롭다.
최대 힙을 쓸 때는 최대 힙 클래스를 정의해 만드는 것이 좋을 것 같다.
📚 참고
backend-developer