[자료구조] 힙(heap)이란

힙(heap) 자료구조란?

완전 이진 트리를 기본으로 한 자료구조로서, 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안되었다.

 

여기서 완전 이진 트리란, 마지막 레벨을 제외한 모든 레벨의 node가 완전히 채워져 있으며 마지막 레벨의 노드들은 가능한 한 왼쪽부터 채워져 있는 구조를 말한다.

완전 이진 트리에 대해서는 이 글을 참고하면 좋을 것 같다.

 

heap의 형태

 

힙의 종류

힙의 종류에는 두가지가 있다.

부모 노드의 값이 자식 노드의 값보다 항상 큰 힙을 최대 힙(max heap), 부모 노드의 값이 자식 노드의 값보다 항상 작은 힙을 최소 힙(min heap)이라고 한다. 값의 대소 관계는 부모 노드와 자식 노드 간에만 성립하고, 형제 노드 간에는 성립하지 않는다는 특징을 갖는다.

 

max heap

min heap

힙의 구현

• 힙을 저장하는 표준 자료구조는 배열이다. (물론 배열이 아닌 다른 것으로 구현해도 된다.)
• 배열을 이용할 때, 쉬운 구현을 위해 0번째 인덱스는 이용하지 않는다.

힙에서 부모 노드와 자식 노드는 일정한 관계를 갖는다.

• 왼쪽 자식의 인덱스 = (부모 인덱스) * 2
• 오른쪽 자식의 인덱스 = (부모 인덱스 * 2) + 1
• 부모 인덱스 = (자식 인덱스) / 2

힙의 삽입

힙에 새로운 요소를 삽입 시, 새로운 요소를 먼저 힙의 마지막 노드에 삽입한다. 이 때, 삽입은 인덱스 순으로 가장 마지막 위치에 삽입한다.

새로운 노드를 부모 노드들과 교환하며 최대힙 또는 최소힙의 성질을 만족시키도록 구조를 변형시킨다.

 

최소 힙에서의 삽입

힙의 삭제는 힙의 삽입과는 다르게 루트 노드가 삭제된다. (최대 힙의 경우 루트 노드는 최댓값, 최소 힙의 경우 루트 노드는 최솟값이다.)

삭제된 루트 노드에는 힙의 인덱스 마지막 노드를 가져오고, 루트 노드부터 자식 노드와 비교해가며 힙의 성질을 만족시키도록 스위칭한다.