잡다한기술블로그

힙 트리란?

힙(Heap)은 완전 이진 트리의 일종으로, 특정한 조건을 만족하도록 정렬된 트리 구조입니다. 힙은 보통 우선순위 큐(Priority Queue)를 구현하기 위해 사용되며, 최소 힙(Min-Heap)과 최대 힙(Max-Heap)으로 나뉩니다.

힙 트리의 특징

1. 완전 이진 트리:
   • 힙은 항상 완전 이진 트리 형태를 유지합니다.
   • 이는 모든 레벨이 꽉 차 있어야 하며, 마지막 레벨은 왼쪽부터 차례로 채워져야 함을 의미합니다.
2. 힙 속성:
   • 최소 힙(Min-Heap):
     • 부모 노드의 값이 자식 노드의 값보다 작거나 같습니다.
     • 루트 노드는 항상 최솟값을 가집니다.
   • 최대 힙(Max-Heap):
     • 부모 노드의 값이 자식 노드의 값보다 크거나 같습니다.
     • 루트 노드는 항상 최댓값을 가집니다.
   • 힙 속성(최소 힙 또는 최대)은 트리의 전체적 구조가 아닌 부모-자식 간의 관계에 의해서만 보장
3. 사용 사례:
   • 우선순위 큐 구현
   • 정렬 알고리즘(힙 정렬)
   • 작업 스케줄링

힙 트리의 동작

1. 삽입 연산

새로운 요소를 힙에 삽입할 때는 완전 이진 트리의 형태를 유지하기 위해 마지막 위치에 삽입한 후, 힙 속성을 만족하도록 재구성합니다.

예시: 최소 힙에 삽입

초기 상태:

    10
   /  \
  20  30
 /
40

1. 50 삽입: 새로운 요소를 마지막 위치에 삽입.

    10
   /  \
  20   30
 /  \
40  50

2. 힙 속성 확인: 부모 노드와 비교하여 최소 힙 속성을 만족하므로 재구성 불필요.

예시: 최대 힙에 삽입

초기 상태:

    50
   /  \
  30  40
 /
20

1. 60 삽입: 새로운 요소를 마지막 위치에 삽입.

    50
   /  \
  30   40
 /  \
20  60

2. 힙 속성 확인: 삽입한 노드(60) > 부모 노드(30), 두 노드의 값을 교환.

    50
   /  \
  60  40
 /  \
20  30

3. 힙 속성 확인 반복: 삽입한 노드(60) > 부모 노드(50), 두 노드의 값을 교환.

    60
   /  \
  50  40
 /  \
20  30

2. 삭제 연산

힙에서 삭제는 보통 루트 노드(최솟값 또는 최댓값)를 제거하는 연산입니다. 루트 노드를 제거한 후, 마지막 노드를 루트로 이동시키고 힙 속성을 유지하도록 재구성합니다.

예시: 최소 힙에서 삭제

초기 상태:

    10
   /  \
  20  30
 /  \
40  50

1. 루트 노드(10) 제거: 마지막 노드(50)를 루트로 이동.

   50
  /  \
 20  30
 /
40

2. 힙 속성 복구: 루트(50) > 자식 노드(20), 두 노드의 값을 교환.

   20
  /  \
 50  30
 /
40

3. 힙 속성 확인 반복: 루트(50) > 자식 노드(40), 두 노드의 값을 교환.

   20
  /  \
 40  30
 /
50

예시: 최대 힙에서 삭제

초기 상태:

    60
   /  \
  50  40
 /  \
20  30

1. 루트 노드(60) 제거: 마지막 노드(30)를 루트로 이동.

   30
  /  \
 50  40
 /
20

2. 힙 속성 복구: 루트(30) < 자식 노드(50), 두 노드의 값을 교환.

   50
  /  \
 30  40
 /
20

3. 힙 속성 확인 반복: 추가 재구성 불필요.

힙 트리의 장점과 단점

장점:

• 삽입 및 삭제가 O(log n)의 시간 복잡도를 가짐.
• 우선순위 큐를 효율적으로 구현 가능.

단점:

• 중간 검색이나 특정 값의 삭제는 비효율적(O(n)).
• 배열 기반 구현 시 동적 크기 조정이 필요할 수 있음.

마무리

힙은 특정 조건을 만족하는 완전 이진 트리로, 효율적인 삽입, 삭제 연산이 가능하여 다양한 알고리즘과 데이터 구조에서 활용됩니다. 최소 힙과 최대 힙의 동작 방식을 이해하면, 우선순위 큐 구현과 힙 정렬과 같은 응용 문제를 효율적으로 해결할 수 있습니다.

뭔가 쓰는 중…