heap (heapq 모듈)

Heap?

• 최댓값과 최소값을 빠르게 찾기 위한 완전 이진트리 기반 자료구조
• 인덱스 n번째 노드의 자식노드가 2개라고 하면 왼쪽 자식 노드의 인덱스는 2n, 오른쪽 자식 노드의 인덱스는 2n+1

최소힙(Min Heap)

• 각 노드가 해당 노드의 자식 노드보다 크지 않거나 작은 완전이진트리!

최대힙(Max Heap)

• 각 노드가 해당 노드의 자식 노드보다 작지 않거나 큰 완전이진트리!

---

heapq 모듈

• 파이썬에 기본 모듈로 바로 import 해서 사용할 수 있다.
• 기본적으로 최소 힙(Min Heap)을 사용한다!!

import heapq

heappush()

• heap에 item 추가하기

import heapq

heap = []
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 5)
heapq.heappush(heap, 2)
heapq.heappush(heap, 6)
print(heap)

// [6, 7, 10, 15, 12, 17]

heapify(list)

• heapify() 함수의 인자에 리스트를 넣어주면 바로 힙으로 변환한다.

import heapq

heap = [6, 15 ,10 ,7, 12, 17]
heapq.heapify(heap)
print(heap)

// [6, 7, 10, 15, 12, 17]

heappop()

• 힙에서 가장 작은 원소를 제거한다.
• 당연히 heapq 모듈을 사용해서 만든 힙 리스트에서 첫번째 원소가 반환된다!

import heapq

heap = [6, 15 ,10 ,7, 12, 17]
heapq.heapify(heap)
# [6, 7, 10, 15, 12, 17]
heapq.heappop(heap)
print(heap)

// [7, 12, 10, 15, 17]

Max Heap 만들기!!

• Heap에 원소를 추가할 때 (-num, num)와 같은 튜플 형태로 값을 넣어주면 튜플의 첫번째 원소를 기준으로 최소 힙을 만들기 때문에 실제 값인 두번째 원소를 기준으로는 최대 힙(Max Heap)이 만들어진다!

import heapq

heap = [6, 15 ,10 ,7, 12, 17]
max_heap = []
for num in heap:
    heapq.heappush(max_heap, (-num, num))
print(max_heap)

// [(-17, 17), (-12, 12), (-15, 15), (-6, 6), (-7, 7), (-10, 10)]