[Section 5] 힙(Heap)의 개념과 용어 정리

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

힙(Heap)은 트리(Tree)의 일종이지만, 일반적인 트리와 다르게 각 노드의 값은 그 노드의 아이(children) 노드 값과 비교하는 조건을 가지고 있다. 이것이 힙의 기본 개념이다. 이 기본 개념을 기반으로 힙을 더 자세히 이해해 보도록 하자.

1. 개념 이해 _ 힙 속성(Heap Property)

힙 속성은 힙의 특징을 결정짓는다. 그 특징은 트리의 노드 비교 조건과 높이 속성에 달려있다. 힙 속성에 대해 이해하기 위해서는 완전 이진트리(Complete binary tree)에 대해 알아야 한다. 예를 들어 다음의 이진트리를 참고하자. 

 

완전 이진 트리 _ 예시

 

위의 완전 트리 예시에서 각 숫자는 노드의 데이터를 의미한다. 그리고 어떤 아이(children) 노드를 시작으로 잡더라도, 트리의 노드 조건은 항상 그 노드의 부모 노드보다 숫자가 크다는 것을 알 수 있다. 따라서 위의 완전 이진트리는 힙이 되기 위한 최소 조건을 만족한다. 그리고 이 조건을 '힙 속성(heap property)'이라고 한다.

 

* 힙 속성은 어떤 트리가 힙이 되기 위한 '최소 힙(basic requirement of a heap)' 기준을 제시한다.

 

2. 힙 용어 정리

• 이진 힙(Binary Heap)은 잎 노드를 제외한 모든 노드가 2개의 아이 노드를 가지는 힙을 의미한다. 
• 힙 속성에 따라 힙은 크게 두 종류로 나뉜다. 만약 트리의 레벨이 높아질수록 노드의 우선순위 값이 같거나 더 작아진다면, 그것은 최소 힙(Min heap)이라 부른다. 반대의 경우, 최대 힙(Max heap)이라고 한다. 다음의 예시를 참고 하자.

최소 힙과 최대 힙 _ 예시

 

• 힙에 새로운 요소를 삽입하는 것은 힙 속성에 따른 정렬을 요구한다. 이 정렬 과정을 힙 구조화(Heapifying)라고 부른다. 그리고 이 과정은 노드의 비교를 통해 정렬 조건에 맞도록 두 노드를 교환을 요구한다. 이 교환 과정을 스왑(Swap)이라고 한다. 자세한 과정은 힙 알고리즘을 통해서 배워보자.

 

* 우선순위 큐에 힙이라는 알고리즘이 존재한다는 것을 기억하자.