힙(Heap) 자료구조

힙이란

힙은 최댓값이나 최솟값을 빠르게 꺼내기 위한 자료구조다.

완전이진트리 모양을 기본으로 하고, 부모와 자식 사이의 대소 관계를 유지한다.

우선순위 큐를 구현하는 대표적인 방법이다.

구조와 두 유형

마지막 레벨을 제외한 모든 레벨이 채워진 완전이진트리 모양이다.

최대 힙은 부모 키가 자식 키보다 크거나 같다. 루트에는 최댓값이 온다.

형제 노드끼리는 대소 관계를 정하지 않는다.

최소 힙은 방향만 반대이며, 루트에 최솟값이 온다.

배열 표현

힙은 배열로 저장하며, 인덱스를 1부터 쓰면 계산이 간단하다.

부모는 i를 2로 나눈 몫, 왼쪽 자식은 2i, 오른쪽 자식은 2i+1이다.

노드 번호 i=5의 부모 위치를 계산해 보자.

삽입 과정

앞 문제의 정답은 2다. 5를 2로 나눈 몫이 부모 인덱스다.

삽입은 새 키를 배열 말단에 추가하는 것으로 시작한다.

부모와 비교해 위반하면 교환한다. 이를 상향 교환, sift-up이라 한다.

삭제 과정

삭제는 루트 값을 꺼내 반환하는 것으로 시작한다.

말단 노드를 루트로 옮기고 말단은 제거한다.

루트에서 우선순위가 높은 자식과 비교해 교환한다. 이를 하향 교환, sift-down이라 한다.

자식이 없을 때까지 같은 과정을 반복한다.

비교와 정리

앞 문제 정답은 최댓값이다. 최대 힙의 루트는 전체 최댓값이다.

두 힙은 구조가 같고, 부모와 자식의 대소 방향만 반대다.

루트 위치와 추출 대상을 두 축으로 나눠 설명하면 된다.

힙을 이진 탐색 트리로 보는 것은 흔한 실수다.