파이썬 heapq

파이썬 문법

토리쟁이 2024. 3. 2. 04:29

힙 자료구조에 대해 공부해보자.

heap

최대값과 최소값을 찾는 연산을 빠르게 하기 위해 고안된 완전 이진 트리를 기반으로 함
특정한 규칙을 가지는 트리
부모 노드와 자식 노드 사이에 대소 관계 성립
최대 힙(max heap): 부모 노드가 자식 노드의 값과 같거나 더 큰 힙
최소 힙(min heap): 부모 노드가 자식 노드의 값과 같거나 더 작은 힙
부모 노드와 자식 노드 사이에 항상 대소 관계가 일정하다는 특징으로 인해, 힙의 루트 노드는 항상 모든 노드들 중에 가장 큰/작은 값을 가지기 때문에, 이를 활용하여 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.
heap 자료구조를 이용하여 우선 순위를 쉽게 정할 수 있다는 장점이 있으며, 이러한 우선 순위 힙을 활용한 대표적인 알고리즘으로는 다익스트라 알고리즘이 있다.

파이썬에서는 데이터를 정렬된 상태로 저장하기 위해서 사용하는 heapq 내장 모듈을 제공한다.

heapq 모듈

이진트리 기반의 최소 힙 자료구조 제공
- 최대 힙을 구현하기 위해서는 (우선순위, 값) 구조의 튜플을 힙에 넣어서 사용하면 된다.
- 넣는 원소 값에 -를 붙이면 최대 힙으로 활용이 가능하다.
최대/최소값을 구할 때 많이 사용
보통 우선순위 큐를 구현하기 위해 사용됨(단, min heap으로 구현되어 있으므로 주의할 것)
시간 복잡도는 삽입/삭제 모두 O(log n)
파이썬 내장 모듈이므로, 특별한 설치 작업이 필요없이 import 해서 사용하면 된다.
- import heapq
heapq 모듈은 리스트를 최소 힙처럼 다룰 수 있도록 하기 때문에, 빈 리스트를 생성한 후 heapq의 함수를 호출할 때마다 리스트를 인자로 넘기면 된다.
힙 원소 추가
- heapq.heappush(heap, data) : heap에 data 추가 (여기서 heap은 리스트)
- heapq.heappush(hq, 3)
- (hq = [ ])
힙 원소 접근
- 인덱싱을 통해 접근 가능
- hq[0]
힙 원소 제거
- heapq.heappop(heap) : heap에서 가장 작은 원소를 pop하여 return
  - heap이 비어있는 경우, IndexError 발생
- heapq.heappop(hq)
리스트 → 힙 변환
- heapq.heapify(list) : 리스트인 list를 heap으로 변환 O(N)
- heapq.heapify(temp)

heapq에서 제공하는 heappush와 heapify 메서드를 비교하는 포스팅이 있으니 참고하면 좋을 것 같다.

heappush vs. heapify 왜 다를까 / 힙 자료구조

문제를 풀다가 궁금증이 생겼다. 같은 배열을 heapq 모듈을 사용하여 heap 자료구조를 만드는데 heappush 방식과 heapify 방식의 결과가 다르다. 힙(heap)이란? 힙은 "부모 노드가 자식보다 작거나 같은

ninefloor-design.tistory.com

참고