Python: heapq 활용하기

heapq

이진트리 기반의 최소 힙 자료구조를 사용할 수 있다. 만약 자료구조를 정렬된 상태로 유지할 필요가 있을 경우 계속해서 정렬을 하는 것 보다는, heapify하는 것이 효율적이다.

import heapq

heap = []
heapq.heappush(heap, 7)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)

heapq.heappop(heap)

• 리스트를 만들고 리스트에 값을 삽입 삭제 할 경우, heapq의 메소드를 사용하면 최소힙 성질을 가진다.
• 최소힙의 경우, 모든 원소(k)는 자식 원소들(2k+1, 2k+2) 보다 크기가 작다.
  • 따라서 해당 예제는 [1, 3, 5, 7]로 정렬되어 최소힙이 유지되게 된다.
• heappop()을 할 경우, 값을 삭제하고 루트 노드의 값을 반환한다.
  • 값을 삭제하지 않고 루트 노드의 값을 가져오려면 리스트 처럼 heap[0]를 통해 접근하면 된다.

heap = [1, 3, 9, 10, 4]
heapq.heapify(heap)

• 기존의 리스트를 최소힙으로 만들기 위해서는 heapify를 사용하면 된다.

heapq 응용

최대 힙

import heapq
heap = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15] 
heapq._heapify_max(heap)
heapq._heappop_max(heap)

• heapq 내에서 제공하는 _heapify_max, _heappop_max를 사용하면, 최대 힙 구조를 간략히 생성할 수 있다.
  • 하지만 이 방법을 사용하면, heappush_max가 없어 추가, 삭제가 계속 필요한 경우 사용이 불가능한다.

import heapq

nums = [1, 3, 9, 10, 4]
heap = []

for num in nums:
    heapq.heappush(heap, (-num, num))

root = heapq.heappop(heap)[1]

• _heapify_max, heappop_max는 힙의 원소가 삽입, 삭제가 반복되는 경우에는 사용할 수 없다. 따라서 기존의 최소힙 성질과 튜플을 이용해 간단히 최대 힙처럼 사용할 수 있다.
• 튜플을 이용해 (-num, num)과 같이 음수 값을 같이 삽입한다.
• 접근할때 heappop(heap)[1]로 접근하여 튜플의 2열에 접근하여 원래의 값을 가져온다.

---