파이썬에서 지원하는 heapq모듈을 사용하면 간단히 구현이 가능하다.
Heapq 모듈
heapq 모듈은 다음과 같은 특징을 가지고 있다.
- 최소힙구조 (최소힙의 형태로 정렬한다)
- 모든 k에 대하여 heap[k] <= heap[2*k+1] 또는 heap[k] <= heap[2*2+2] 의 공식을 만족한다.
- 가장작은 요소가 heap[0]에 위치한다.
- 힙을 만들기 위해서는 초기화된 리스트를 사용하거나 heapify를 통해 값이 들어있는 리스트를 힙으로 변환가능하다.
heapq 모듈 사용
import heapq파이썬에서 지원하는 내장모듈이기 때문에 별도의 설치없이 import 하나만으로도 사용할 수 있다.
heap = [] # 힙으로 사용할 빈 리스트 생성heapq모듈은 파이썬의 리스트를 최소힙 형태로 정렬하기 때문에 빈 리스트를 생성한 뒤, 모듈 함수를 호출 할 때 마다 생성한 리스트를 인자 값으로 넘겨서 사용한다. 즉, 추가/삭제만 해도 알아서 정렬을 해준다 .
데이터 삽입
힙에 데이터를 삽입할 때는 heappush() 함수를 이용하여 원소를 삽입 할 수 있다. 첫번째 인자로는 대상 리스트, 두번째 인자로는 삽입할 원소 값을 입력해주면 된다.
위에서 작성한 모듈을 import한 후 리스트를 선언하는 부분과, 데이터 삽입하는 과정을 코드로 나타내면 아래와 같이 작성 가능하다.
import heapq
heap = []
heapq.heappush(heap, 10)
heapq.heappush(heap, 5)
heapq.heappush(heap, 6)
heapq.heappush(heap, 15)
heapq.heappush(heap, 4)
heapq.heappush(heap, 9)
print(heap) # 출력 : [4, 5, 6, 15, 10, 9]데이터 삭제
모듈의 heappop() 함수를 이용하여 원소를 삭제할 수 있다. 대상리스트를 인자로 넘기면, 최솟값을 삭제한 뒤에 반환해준다.
print(heapq.heappop(heap)) # 4
print(heap) # [5, 9, 6, 15, 10]위에서 원소를 삭제하고 heap값을 출력한 것을 보면 원소가 작은 순서대로 정렬되어 출력되지 않는 것을 확인할 수 있다.
최소힙은 최솟값을 빠르게 찾기 위한 알고리즘이지, 작은 순서대로 정렬하는 알고리즘은 아니다. 그렇기때문에 작은 순서대로 정렬되어 있을 것이라고 생각하면 안된다 !
만약, 원소값을 삭제하기 않고 최솟값을 출력만 하고 싶다면 아래와 같이 작성하면 된다.
print(heap[0]) # 5heapify 사용
다음은 리스트를 힙으로 변환하는 방법에 대해 알아보겠다.
이미 원소가 삽입되어 있는 리스트를 heapq 모듈을 사용하여 힙으로 변환하는 것이 가능하다. 이때는 heapify() 함수를 사용하고 인자로 대상 리스트를 전달하면 된다.
hq = [7,2,4,3,1]
print(hq) # [7, 2, 4, 3, 1]
heapq.heapify(hq)
print(hq) # [1, 2, 4, 3, 7]
파이썬에서 heapq모듈을 지원해줘서 힙구현이 매우매우 간단해진것 같다. 힙을 공부하며 더 세부적인 내용은 그때그때 추가해서 정리해둬야지 ..
일단 위의 내용을 가지고 힙 알고리즘 문제를 풀러 가봐야겠다 !
