[자료구조] 힙[heap]이란?

• 힙은 우선순위 큐를 위해 고안된 완전 이진 트리 형태의 자료구조로, 최대값과 최소값을 빠르게 찾아내는 데 유리하며, 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 작은 반정렬 상태를 유지한다.

• 힙의 종류에는 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 최대 힙(max heap)과, 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 최소 힙(min heap)이 있다.

• 최소 힙에 데이터를 저장할 때는 새 노드를 맨 끝에 저장한 후 부모 노드와 비교하여 위치를 조정하고, 삭제할 때는 루트 노드를 반환하고 마지막 노드를 루트 자리에 옮긴 후 자식 노드와 비교하여 위치를 조정한다.

• 파이썬에서 우선순위 큐를 구현할 때는 `PriorityQueue`와 `heapq` 모듈을 사용할 수 있으며, `heapq`는 최소 힙 구조로 작동하며 `heappush`, `heappop`, `heapify` 등의 함수를 제공한다.