[자료구조] 힙(heap), 최소힙, 최대힙

힙(heap)

heap은 '최댓값 및 최솟값을 찾아내는 연산'을 빠르게 하기 위해 고안된 완전 이진트리를 기본으로 한 자료구조

A가 B의 부모 노드이면, A의 키 값과 B의 키 값 사이에는 대소 관계가 성립함
형제 노드 사이에서는 대소 관계 정해지지 않음

최소힙

부모 노드의 키 값이 자식 노드의 키 값보다 항상 작은 힙
가장 작은 값을 가지는 노드가 항상 루트에 오게 됨

최대힙

부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 힙
가장 큰 값을 가지는 노드가 항상 루트에 오게 됨

heapq 라이브러리

heapq 모듈은 리스트를 최소 힙 처럼 다룰 수 있도록 제공함

heapq 메소드

• heapq.heappush(list, item) : list에 item을 추가
• heapq.heappop(list) : list에서 가장 작은 원소(루트)를 pop
• heapq.healify(list) : list를 힙으로 변환함 O(N)

heapq를 이용한 최대힙 구현

heapq 모듈은 기본이 최소힙 형태이기 때문에 최대힙으로 사용하기 위해서는 간단한 트릭이 필요하다.

힙에 item을 추가할 때 (-item, item) 형태의 튜플을 삽입하면 -로 인해 가장 큰 값이 가장 작은 값으로 변환되고 이는 최소힙 형태인 heapq에서 루트에 위치하게 된다.
기존 값을 pop하여 사용하고 싶을 때는 heapq.heappop(list)[1]을 통해 튜플의 두번째 값을 사용하면 된다.