힙(Heap)

힙은 완전 이진 트리의 일종으로, 부모 노드와 자식노드가 특정한 조건을 만족하는 자료구조를 말합니다.

📢 완전 이진 트리

부모 노드 밑에 자식 노드가 최대 2개까지 있을 수 있고, 마지막 레벨을 제외한 모든 레벨의 노드가 완전히 채워져 있는 트리 구조

1. 힙의 특징

  • 힙에서 부모는 최대 2개의 자식 노드를 갖습니다.
  • 힙은 가능한 가장 적은 공간을 차지합니다. 다음 레벨로 내려가기 전에 모든 노드(왼쪽/오른쪽 노드)가 다 채워집니다.
  • 같은 레벨에서는 왼쪽 자식이 언제나 먼저 채워집니다.
  • 형제 노드 사이에는 어느 관계도 존재하지 않는다.

2. 힙의 종류

1) 최대 힙(Max-Heap)

각 부모 노드의 값이 자식 노드의 값보다 크거나 같은 완전 이진 트리입니다. 루트 노드에는 항상 최대값이 위치합니다.

2) 최소 힙 (Min-Heap)

각 부모 노드의 값이 자식 노드의 값보다 작거나 같은 완전 이진 트리입니다. 루트 노드는 항상 최소값이 위치합니다. Image

3. 힙 구현 방법

  • 힙은 보통 배열(Array)을 이용하여 구현합니다.
  • 아래 그림과 같이 루트 노드(9)는 배열의 첫번째 인덱스에 위치하게 됩니다.
  • 인덱스가 1부터 시작하는 배열의 경우, i 인텍스에 있는 노드의 왼쪽 자식 노드는 2 * i 인덱스에 위치하며,

  • 오른쪽 자식 노드는 2 * i + 1 인덱스에 위치하게됩니다.

    Image

  • 첫 번째 인덱스가 0인 배열을 사용하는 경우에 노드가 인덱스 i에 있을 때,
  • 왼쪽 자식 노드는 인덱스 2 * i + 1에, 오른쪽 자식 노드는 인덱스 2 * i + 2에 위치합니다.
  • 또한, 자식 노드의 부모 인덱스는 (i - 1) / 2 (정수 나눗셈)로 계산할 수 있습니다.

4. 주요 연산 및 알고리즘

1) 힙 삽입 (Insertion)

Image

  • 절차:
    1. 새 요소를 힙의 끝(배열의 마지막 위치)에 추가합니다.
    2. 새 요소를 부모 노드와 비교하여, 힙 속성이 깨진 경우 서로 교환합니다. (예: 최대 힙에서 새 요소가 부모보다 큰 경우)
    3. 이 과정을 힙 속성이 만족될 때까지 반복합니다.
  • 시간 복잡도: O(log n)

2) 힙 삭제 (Deletion)

  • 일반적으로 루트 노드 삭제 → 힙 자료구조는 최대값과 최소값을 이용하는 것이 목적이기 때문

Image

Image

  • 절차:
  1. 루트 노드를 제거합니다(최대 힙에서는 최대값, 최소 힙에서는 최소값)
  2. 힙의 마지막 요소를 루트로 이동합니다.
  3. 이동한 요소를 자식 노드와 비교하여 힙 속성을 만족하지 않으면, 더 적절한 자식과 교환합니다.
  4. 이 과정을 힙 속성이 만족될 때까지 반복합니다.
  • 시간 복잡도: O(log n)

5. 힙의 사용사례

힙은 데이터를 관리하는데 있어서 다양한 상황에서 유용하게 사용됩니다. 그 중 많이 사용하는 사례는 우선 순위 큐(Priority Queue)입니다.

우선순위 큐:

힙은 우선순위 큐(Priority Queue)를 구현하는 데 널리 사용됩니다. 삽입, 삭제, 최댓값/최솟값 검색 연산이 모두 효율적입니다.

참고

힙 (최소 힙, 최대 힙)

[자료구조 개념 이해하기 ‘힙과 힙 정렬 알고리즘’ 요즘IT](https://yozm.wishket.com/magazine/detail/2312/)

[알고리즘] 힙(Heap) 자료구조

[알고리즘] 힙(Heap)