파이썬 자료구조 힙_Python heaps

 

힙은 최댓값 or 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전이진트리를 기본으로 하는 트리

 

heap property: A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소관계가 성립

- 최소 힙(Min Heap): 부모 노드의 키값이 자식 노드의 키값보다 항상 작은 힙

- 최대 힙(Max Heap): 부모 노드의 키값이 자식 노드의 키값보다 항상 큰 힙

 

 

* 파이썬 힙 자료구조

heapq 모듈에서 heapq 알고리즘 제공

  - heapq는 내장 모듈로 별도의 설치가 필요하지 않음

  - 최소 힙 형태로 정렬됨 (0번째 인덱스부터 시작해 k번째 원소가 항상 자식원소들(2k+1, 2K+2)보다 작거나 같음)

 

https://www.geeksforgeeks.org/heap-data-structure/

힙 함수 명령어

- heapq.heappust(heap, item): item을 heap에 추가

- heapq.heappop(heap): heap에서 가장 작은 원소를 pop + return, 비어있는 경우 IndexError

- heapq.heapify(x): 이미 선언되어 있는 리스트 x를 heap으로 변환, (O(N))

 

import heapq

# 1 - heappush
heap = []
heapq.heappush(heap, 5)
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)

print(heap)
>>> [5, 1, 2]

# 1.1 - heapify
list_to_heap = [5, 1, 2]
heapq.heapify(list_x)

print(list_to_heap)
>>> [5, 1, 2]


# 원소 삭제
result = heapq.heappop(heap)

print(result)
print(heap)
>>> 1
>>> [2, 5]

 

파이썬은 최소힙 (min heap)을 기본으로 하는데, 최대힙으로 만들기 위해서는 대소관계를 뒤집어 줄 필요가 있음

: 튜플을 사용하면 되는데, 튜플의 첫 번째 원소를 우선순위로 힙을 구성

# max_heap
heap_items = [1,3,5,6,9]

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

print(max_heap)
>>> [(-9, 9), (-6, 6), (-5, ,5), (-3, 3), (-1, 1)]


# max_heap 원소 찾기
max_item = heapq.heappop(max_heap)[1]
print(max_item)
>>> 9