힙(Heap)에 대해서 알아보자

---

안녕하세요, 오늘은 자료구조 중 힙(Heap) 에 대하여 공부해 보겠습니다.

힙(Heap)이란?

• 완전 이진 트리(Complete binary DecisionTreeClassifier)의 일종으로, 우선순위 큐(Priority Qeueu)를 위하여 만들어진 자료구조입니다.

• 특히, 최댓값 / 최솟값을 찾는 것에 최적화 되어있습니다.

힙(Heap)의 종류

힙(heap)은 최대 힙(Max heap) 과 최소 힙(Min heap) 으로 나눌 수 있습니다.

최대 힙(Max heap) 은 부모 노드의 키 값이 자식 노드보다 크거나 같은 형태이고,
최소 힙(Min heap) 은 부모노드의 키 값이 자식 노드보다 작거나 같은 형태입니다.

그렇다면 트리 구조 형태의 heap은 배열상에서 어떤 인덱스 구조를 가지고 있을까요? 기본적으로, 루트 노드를 배열의 0번 인덱스에 저장한 후에, 각 계층별로 왼쪽 자식 노드를 먼저 인덱스에 할당해줍니다. 아래 그림을 보시면 직관적으로 이해가 되실 겁니다.

위 예제는 최대 힙으로, 가장 작은 인덱스(=0)에 가장 큰 수(=10)가 할당되어 있습니다. 그 아래 계층에는 왼쪽에 9, 오른쪽에 5가 있으니 차례대로 다음에 올 인덱스에 넣어줍니다(1번 인덱스에 왼쪽 자식인 9, 2번 인덱스에 오른쪽 자식인 5). 같은방식으로 모든 인덱스에 할당할 수 있습니다.

Python에서 Heap 사용하기

python에서는 힙(heap) 자료구조를 편하게 사용할 수 있도록 라이브러리가 내장되어 있습니다.
heapq 모듈을 사용하면 최소 힙의 형태로 제공 받을 수 있습니다.
아래는 사용 예시입니다.

• heapq.heapify(x) : 리스트 x를 heap으로 변환
• heapq.heappush(heap, item) : item을 heap에 추가
• heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & return. 비어있는 경우 Index error 호출

활용예제

최댓값과 최솟값을 빠르고 효율적으로 구해야하는 경우에, 힙을 활용해서 문제를 할 수 있다면 힙에 대한 이해도 잘 되었다고 할 수 있겠죠? 백문이 불여일코딩! 프로그래머스의 연습문제를 통해서 힙에 대한 이해도를 높여 봅시다.

저는 처음에 힙에 대하여 모르고 문제를 풀어서 많이 해매었는데요, 힙을 공부하고 나니 자연스럽게 풀려서 굉장히 뿌듯했습니다.

제가 푼 정답은 이 곳에서 확인하실 수 있습니다.

References

heejeong Kwon님의 블로그
emplam27님의 블로그
아기여우님의 블로그