힙(Heap)

힙은 여러 개의 값 중에서 가장 크거나 작은 값을 빠르게 찾기 위해 만든 완전 이진 트리입니다.

 

완전 이진 트리 구조

완전 이진 트리 예시:
       10
      /  \
     8    9
    / \  /
   4  7 3

특징:
- 마지막 레벨을 제외한 모든 레벨이 완전히 채워짐
- 마지막 레벨은 왼쪽부터 순서대로 채워짐
- 배열로 구현하기 최적화된 구조

 

 

힙의 종류

 

최대힙 (Max Heap)

부모 노드의 값은 자식 노드의 값보다 항상 큰 규칙을 지키는 힙

최대힙 예시:
       100          ← 루트(최댓값)
      /   \
     80    90       ← 부모 ≥ 자식
    / \   / \
   50 70 60 85     ← 모든 레벨에서 규칙 적용

규칙: parent ≥ left_child, parent ≥ right_child
결과: 가장 큰 값을 O(1)에 찾을 수 있음

 

 

최소힙 (Min Heap)

부모 노드의 값은 자식 노드의 값보다 항상 작은 규칙을 지키는 힙

최소힙 예시:
        10          ← 루트(최솟값)
      /   \
     20    15       ← 부모 ≤ 자식  
    / \   / \
   30 25 40 35     ← 모든 레벨에서 규칙 적용

규칙: parent ≤ left_child, parent ≤ right_child
결과: 가장 작은 값을 O(1)에 찾을 수 있음

 

 

이진탐색트리 vs 힙

 

이진탐색트리 (BST)

탐색을 쉽게 하기 위해 왼쪽이 더 작고 오른쪽이 큰 값으로 꼭 구성

이진탐색트리:
       50
      /  \
     30   70        ← 왼쪽 < 부모 < 오른쪽
    / \   / \
   20 40 60 80

규칙: left < parent < right
목적: 탐색 최적화 (O(log n))

 

 

힙

부모-자식 간의 대소관계만 중요, 좌우 관계는 상관없음

최대힙:
       80
      /  \
     70   60        ← 좌우 순서 무관
    / \   / \
   50 65 40 30

규칙: parent ≥ children (좌우 순서 무관)
목적: 최댓값/최솟값 빠른 접근 (O(1))

 

 

핵심 차이점 요약

특성	이진탐색트리	힙
좌우 순서	중요 (left < parent < right)	무관
탐색	O(log n)	O(n)
최댓값/최솟값	O(log n)	O(1)
삽입/삭제	O(log n)	O(log n)
용도	검색, 정렬	우선순위 큐

 

시간복잡도

• 참조 (루트 노드): O(1) - 최댓값/최솟값 즉시 접근
• 탐색 (특정 값): O(n) - 순서가 보장되지 않아 전체 탐색 필요
• 삽입/삭제: O(log n) - 힙 속성 유지를 위한 재정렬