힙(Heap) 완전 정복

01

이진 트리 (Binary Tree)

이진 트리는 각 노드가 최대 두 개의 자식 노드를 가질 수 있는 계층적 자료구조입니다. 왼쪽 자식(left child)과 오른쪽 자식(right child)으로 구분됩니다.

루트 노드 (Root)

트리의 최상단, 부모가 없는 유일한 노드

리프 노드 (Leaf)

자식이 없는 최하단 노드들

높이 (Height)

루트에서 가장 깊은 리프까지의 거리

레벨 (Level)

루트가 레벨 0, 아래로 내려갈수록 +1

힙의 근간이 되는 완전 이진 트리(Complete Binary Tree)는 추가 조건이 있습니다.

    완전 이진 트리의 조건

    ① 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있다.

    ② 마지막 레벨의 노드는 반드시 왼쪽부터 순서대로 채워진다.

완전 이진 트리 (N=10) — 레벨·높이 구조

    핵심 공식: H = ⌊log₂N⌋

    N=10 → H=3  |  N=100 → H=6  |  N=1,000 → H=9  |  N=1,000,000 → H=19

    노드가 1,000배 늘어도 높이는 3배 증가에 불과합니다. 이것이 O(log N)의 근거입니다.

02

힙 (Heap)

힙은 완전 이진 트리에 힙 속성(Heap Property)이라는 추가 규칙을 부여한 자료구조입니다. 최댓값 또는 최솟값을 O(1)에 조회하기 위해 설계되었습니다.

최소 힙 (Min Heap)

부모 ≤ 자식 (항상 성립)
루트 = 전체 최솟값
Java PriorityQueue 기본값

최대 힙 (Max Heap)

부모 ≥ 자식 (항상 성립)
루트 = 전체 최댓값
Collections.reverseOrder() 사용

최소 힙 (Min Heap) — 부모 ≤ 자식이 항상 성립 / 루트 = 최솟값

힙은 완전 정렬이 아닙니다. 부모가 자식보다 작다는 것만 보장하며, 형제 노드 사이에는 순서 보장이 없습니다. (예: 위 트리에서 9와 20의 위치는 바뀌어도 유효한 힙입니다)

03

시간복잡도 — 왜 O(log N)인가

힙의 모든 핵심 연산이 O(log N)인 이유는 하나입니다. 완전 이진 트리의 높이가 ⌊log₂N⌋이기 때문입니다. 삽입과 삭제 모두 트리를 위아래로 한 번만 이동하며, 최대 이동 횟수 = 높이 = log N입니다.

OFFER / PUSH — Heapify Up (위로 올라가기)

새 값을 배열 맨 끝(= 트리 마지막 리프)에 추가한 뒤, 부모보다 작으면 교환하며 위로 올라갑니다. 루트 도달 또는 힙 조건 만족 시 종료합니다.

삽입 시뮬레이션 — 값 3 추가 (최소 힙: [2,5,8,12,9,20,15,25,30,18])

0. 리프 삽입

1. 비교 #1

2. 비교 #2

3. 완료

새 값 3을 맨 마지막 위치(인덱스 10)에 삽입합니다. 완전 이진 트리 구조를 유지합니다.

POLL / POP — Heapify Down (아래로 내려가기)

루트(최솟값)를 꺼내고, 배열 마지막 노드를 루트 자리로 이동합니다. 두 자식 중 작은 쪽과 비교해서 부모가 더 크면 교환하며 아래로 내려갑니다.

삭제 시뮬레이션 — 루트(최솟값 2) 꺼내기

0. 루트 제거, 마지막→루트

1. 자식 비교 #1

2. 자식 비교 #2

3. 완료

루트(2)를 꺼내고, 마지막 노드 18을 루트 자리로 이동합니다.

연산	힙 (PriorityQueue)	정렬 배열	이유
최솟값 조회 peek()	`O(1)`	`O(1)`	루트 = 배열[0] 직접 접근
삽입 offer()	`O(log N)`	`O(N)`	힙: 높이만큼만 / 배열: 자리 찾아 이동
최솟값 삭제 poll()	`O(log N)`	`O(1)`	힙: 재정렬 필요 / 배열: 그냥 제거
임의 검색	`O(N)`	`O(log N)`	힙: 이진탐색 불가 / 배열: 이진탐색 가능

04

배열 인덱스 매핑

힙은 트리 구조이지만 실제 메모리는 1차원 배열에 저장됩니다. 완전 이진 트리를 레벨 순서대로 나열하면 인덱스 산술만으로 부모·자식 위치를 O(1)에 계산할 수 있기 때문입니다. 포인터가 전혀 필요 없고, 메모리가 연속 배치되어 캐시 효율도 우수합니다.

인덱스 공식 (0-based · Java PriorityQueue 기준)
부모 인덱스
(i - 1) / 2
왼쪽 자식
2 * i + 1
오른쪽 자식
2 * i + 2

노드를 클릭하면 부모·자식 인덱스 계산 결과를 확인합니다

배열 표현 (레벨 순서대로)

■ 선택 노드 ■ 부모 ■ 자식

노드를 클릭하면 인덱스 계산 과정을 보여줍니다.

05

우선순위 큐 (Priority Queue)

우선순위 큐는 FIFO(선입선출) 방식의 일반 큐와 달리, 우선순위가 가장 높은(= 값이 가장 작은) 데이터가 항상 먼저 나오는 추상 자료형입니다. 내부 구현으로 힙을 사용합니다.

일반 큐 (Queue)

먼저 들어온 순서대로 나옴 — FIFO
삽입 O(1), 제거 O(1)

우선순위 큐 (PQ)

값이 작을수록 먼저 나옴 — 순서 무관
삽입 O(log N), 제거 O(log N)

    // Java — PriorityQueue 핵심 API
// ① 최소 힙 (기본값) — 작은 값이 먼저 나옴
PriorityQueue<Integer> pq = new PriorityQueue<>();

// ② 최대 힙 — Comparator 역순
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder());

// ③ 주요 메서드
pq.offer(5);   // 삽입 O(log N) — 끝에 추가 후 Heapify Up
pq.peek();    // 최솟값 확인 O(1) — 루트 조회 (제거 안 함)
pq.poll();    // 최솟값 제거 O(log N) — 루트 제거 후 Heapify Down
pq.size();    // 원소 개수 O(1)
pq.isEmpty(); // 비어있는지 O(1)
  

내부적으로 offer()는 배열 끝에 추가 후 Heapify Up을, poll()은 루트 제거 후 마지막 원소를 루트로 올리고 Heapify Down을 실행합니다. 앞서 확인한 O(log N) 과정과 완전히 동일합니다.

06

문제 해설 — 더 맵게

문제 정의 (프로그래머스 Lv.2)

모든 음식의 스코빌 지수를 K 이상으로 만들어야 합니다.
섞는 공식: 새 음식 = 가장 작은 값 + (두 번째로 작은 값 × 2)
최소 횟수를 반환. 불가능하면 -1 반환.

매 단계마다 가장 작은 값 2개를 찾아야 합니다. 이 작업을 반복적으로 효율적으로 수행하는 것이 핵심입니다.

    왜 힙을 써야 하는가?

    배열 재정렬 방식: 매 단계 O(N log N) × 최대 N 단계 = O(N² log N) → 시간 초과

    최소 힙 방식: 꺼내기 O(log N) × 2 + 삽입 O(log N) = 단계당 O(log N), 전체 O(N log N) → 통과

    // ParkYuBin.java — 전체 풀이
public int solution(int[] scoville, int K) {

    // ① 모든 값을 최소 힙에 삽입 — O(N log N)
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int s : scoville) {
        pq.offer(s);
    }

    int count = 0;

    // ② peek()으로 루트(최솟값) 확인 — O(1)
    while (pq.peek() < K) {

        // ③ 원소 1개 남았는데 K 미만 → 불가능
        if (pq.size() == 1) return -1;

        // ④ 가장 작은 두 값 꺼내기 — 각 O(log N)
        int first  = pq.poll(); // 최솟값 → Heapify Down
        int second = pq.poll(); // 두 번째 최솟값 → Heapify Down

        // ⑤ 섞어서 다시 삽입 — O(log N)
        pq.offer(first + second * 2); // Heapify Up
        count++;
    }

    return count;
}
  

풀이 시뮬레이션 · K = 7 · 초기: [1, 2, 3, 9, 10, 12]

힙 배열 상태 (루트 = 맨 왼쪽)

초기 상태. 최솟값 1이 루트. K=7보다 작으므로 섞기를 시작합니다.

    최종 정리

    peek(): 루트 읽기 → O(1)  | 
    offer(): Heapify Up → O(log N)  | 
    poll(): Heapify Down → O(log N)

    전체 시간복잡도: O(N log N) — 완전 이진 트리의 높이가 log N임을 이용한 결과
  