힙은 완전 이진 트리(Complete Binary Tree)를 기본으로 하는 자료구조이다. 힙은 최댓값 또는 최솟값을 빠르게 찾아내는 연산을 위해 고안되었다.

힙의 종류

• 최대 힙(Max Heap): 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리이다.
• 최소 힙(Min Heap): 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리이다.

힙의 특징

• 힙은 완전 이진 트리이므로 배열로 표현하기 적합하다.
• 배열 인덱스가 0부터 시작할 경우:
  • 부모 노드 인덱스 = (자식 노드 인덱스 - 1) / 2
  • 왼쪽 자식 노드 인덱스 = (부모 노드 인덱스 * 2) + 1
  • 오른쪽 자식 노드 인덱스 = (부모 노드 인덱스 * 2) + 2
• 힙은 우선순위 큐(Priority Queue)를 구현하는 데 효율적이다.
• 힙의 높이는 O(log n)이며, 삽입과 삭제 연산의 시간 복잡도는 O(log n)이다.

힙의 주요 연산

요소 삽입

위와 같은 힙에 10을 삽입하는 과정을 나타내겠다. 힙은 완전 이진 트리여야 하므로 새로운 요소는 항상 제일 마지막 레벨의 가장 왼쪽 빈 자리에 삽입된다.

<aside> 💡

다른 케이스

만약 요소 1 자리가 비어 있다면 요소 1자리로 가게 된다. 이는 완전 이진 트리의 속성을 유지하기 위함이다.

</aside>

마지막 위치에 새 요소를 삽입한 후에는 힙의 속성(부모 노드가 자식 노드보다 크거나 같음)을 유지하기 위해 부모 노드와 비교하면서 필요한 경우 위치를 교환한다. 이 과정을 삽입한 노드가 올바른 위치를 찾을 때까지 반복한다.

먼저, 10이 부모 노드 4보다 크므로 두 값을 교환한다.

다음으로, 10이 새로운 부모 노드인 6보다 크므로 다시 두 값을 교환한다.