힙(heap)

힙은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 함. 힙에서는 중복된 값을 허용한다.
(이진 탐색 트리에서는 중복된 값을 허용하지 않는다)

힙의 종류

• 최대 힙(max heap)

  • 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

• 최소 힙(min heap)

  • 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

파이썬 힙 자료구조

heapq는 최소 힙 형태의 알고리즘을 제공한다.

heapq.heappush(heap, item) : item을 heap에 추가
heapq.heappop(heap) : heap에서 가장 작은 원소를 pop, 비어있을 경우 IndexError가 호출
heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함.

힙 생성 & 원소 추가

heapq 모듈은 리스트를 최소 힙처럼 다룰 수 있도록 하기 때문에, 빈 리스트를 생성한 후 heapq의 함수를 호출할 때마다 리스트를 인자에 넘겨야함.

import heapq

heap = []
heapq.heappush(heap, 50)
heapq.heappush(heap, 10)
heapq.heappush(heap, 20)

이미 생성해둔 리스트가 있다면 heapify함수를 통해 즉각적으로 힙 자료형으로 변환할 수 있음

heap2 = [50 ,10, 20]
heapq.heapify(heap2)

힙에서 원소 삭제

result = heapq.heappop(heap)

원소를 삭제하지 않고 가져오고 싶으면 [0] 인덱싱을 통해 접근하면 된다.

result2 = heap[0]

최대힙 만들기

힙에 원소를 추가할때 (-item, item)의 튜플 형태로 넣어주면 튜플의 첫 번째 원소를 우선순위로 힙을 구성하게 됨. 이때 원소값의 부호를 바꿨기 때문에, 최소 힙으로 구현된 heapq 모듈을 최대 힙 구현에 활용하게 됨.

heap_items = [1,3,5,7,9]

max_heap = []
for item in heap_items:
  heapq.heappush(max_heap, (-item, item))

max_item = heapq.heappop(max_heap)[1]