Heap

Heap (힙) — 완전 이진 트리 기반 우선순위 자료구조

특징

• 완전 이진 트리(빈틈 없이 왼쪽부터 채워짐)를 배열로 표현
• MaxHeap: 부모 ≥ 자식 (루트가 항상 최댓값)
• MinHeap: 부모 ≤ 자식 (루트가 항상 최솟값)
• 중복 값 허용 (Set과 다름) — 부모 = 자식이어도 규칙 위반 아님
• 정렬된 상태가 아님 — 루트(최댓값/최솟값)만 O(1)로 보장

배열로 트리를 표현하는 법 (0-based)

완전 이진 트리는 빈틈이 없어 배열에 순서대로 담으면 인덱스만으로 부모·자식을 계산할 수 있음 (포인터 불필요)

관계	인덱스
부모	(i - 1) / 2
왼쪽 자식	2i + 1
오른쪽 자식	2i + 2

시간 복잡도

연산	시간 복잡도
peek (루트 확인)	O(1)
insert (삽입)	O(log n)
poll (루트 제거)	O(log n)
resize (배열 확장)	O(n) (가끔 발생, 분할상환 O(1))

• insert / poll이 O(log n)인 이유: 트리 높이만큼만 이동하기 때문

두 가지 핵심 연산

• siftUp (상향 조정) — insert 시

  • 새 값을 맨 끝(leaf)에 넣고, 부모보다 크면(MaxHeap) 위로 교환하며 올라감
  • 부모가 더 크면 즉시 멈춤 (위쪽은 원래 올바른 힙이므로 볼 필요 없음)

• siftDown (하향 조정) — poll 시

  • 마지막 원소를 루트로 옮기고, 두 자식 중 더 큰 쪽과 비교하며 내려감
  • 자기 자신이 가장 크면 멈춤

왜 항상 올바른 힙이 유지되나 (불변식)

• 시작: 원소 0~1개는 비교 대상이 없어 자동으로 올바른 힙
• insert: 올바른 힙에 leaf 하나만 추가 → 깨질 수 있는 곳은 한 경로뿐 → siftUp으로 복구
• poll: 올바른 힙에서 루트만 제거 → siftDown으로 복구
• 매 연산 후 규칙이 유지되므로 결과는 항상 올바른 힙

그래서 전체 n개를 검사할 필요 없이 한 줄기 경로(log n)만 고치면 충분함

resize (동적 배열 확장)

• 배열은 크기가 고정 → "늘린다"는 건 더 큰 배열을 새로 만들어 값을 복사하는 것
• 꽉 차면 2배로 확장 (1씩 늘리면 매번 복사라 느림 → 2배면 평균 O(1))

build heap (배열을 한 번에 힙으로 만들기)

• 힙이 아닌 배열을 처음부터 힙으로 만드는 과정
• 배열을 그대로 복사한 뒤, 마지막 부모 노드부터 거꾸로 siftDown (parent(size-1) → 0)
• 뒤(아래)에서부터 하는 이유: 아래 서브트리가 먼저 힙이 되어야 위쪽 siftDown이 성립하기 때문
• 리프(전체의 약 절반)는 내려갈 데가 없어 건너뜀 → siftDown 대상은 약 n/2개

시간복잡도: O(n) (O(n log n) 아님)

• 아래층 노드는 많지만 이동 거리가 짧고, 위층 노드는 이동 거리가 길지만 개수가 적음 → 상쇄되어 O(n)
• 반면 하나씩 insert 반복은 O(n log n) (많은 리프가 먼 거리를 siftUp하기 때문)

방식	방향	멀리 이동하는 노드	시간복잡도
insert 반복	siftUp (위로)	리프(많음)	O(n log n)
build heap	siftDown (아래로)	루트 근처(적음)	O(n)

MaxHeap ↔ MinHeap 전환

• 구조(배열 표현, 인덱스 계산, siftUp/siftDown)는 완전히 동일
• 비교 부호만 뒤집으면 됨: MaxHeap compareTo(...) > 0 ↔ MinHeap compareTo(...) < 0
• 라이브러리는 부호를 고치는 대신 Comparator만 교체 (Comparator.reverseOrder())

peek / size / isEmpty

• peek: 꺼내지 않고 최댓값만 O(1)로 확인 — "꺼낼지 말지 먼저 판단"할 때 유용

우선순위 큐 (Priority Queue)

• 큐(FIFO)와 달리 우선순위가 높은 데이터가 먼저 나가는 자료구조 → 힙으로 구현하는 게 일반적
• 힙 기반이면 삽입·삭제 모두 O(log n) (배열·연결 리스트는 한쪽이 O(n))
• 우리가 만든 MaxHeap이 곧 우선순위 큐 구현: insert(추가) / poll(최댓값 삭제·반환) / peek(최댓값 확인)
• "값이 큰 것이 우선"인 규칙이며, 우선순위 기준을 바꾸려면 Comparator 적용

주의: 중복 값과 안정성

• 중복 값은 정상 저장되고, poll 시 개수만큼 그대로 나옴
• 단, 같은 값끼리 "먼저 넣은 게 먼저 나온다"는 보장(안정성)은 없음

정상 동작 검증 방법

1. 정렬 조건: MaxHeap을 poll로 모두 꺼내면 내림차순, MinHeap이면 오름차순인가
2. resize 조건: 초기 capacity를 넘겨 넣어도 (예: 기본 10에 14개 삽입) 값 손실 없이 동작하는가