힙 & 우선순위 큐 (Heap & PriorityQueue)

JayJi·2026년 4월 12일

목록 보기

8/30

문제	난이도	핵심
1927번 — 최소 힙	실버 II	최소 힙 기본 구현
11279번 — 최대 힙	실버 II	최대 힙 기본 구현
11286번 — 절댓값 힙	실버 I	커스텀 Comparator
1655번 — 가운데를 말해요	골드 II	최소 힙 + 최대 힙
23290번 — 마법사 상어와 복제	골드 I	우선순위 큐 응용

1. 개념

힙(Heap)은 완전 이진 트리 기반의 자료구조로, 부모 노드가 항상 자식 노드보다 크거나 작은 조건을 만족한다.

항상 최솟값(또는 최댓값)을 O(1)에 꺼낼 수 있다.

최소 힙 (Min Heap)          최대 힙 (Max Heap)
        1                           9
      /   \                       /   \
     3     5                     7     5
    / \   /                     / \   /
   4   8 7                     3   2 1

부모 ≤ 자식 (항상)           부모 ≥ 자식 (항상)

우선순위 큐(Priority Queue)는 힙으로 구현된다.

2. 동작 과정

최소 힙에 원소 삽입/삭제

삽입 — push(2)

삽입 전       맨 아래에 추가    부모와 비교하며 위로 올라감 (heapify-up)
    1              1                    1
  /   \          /   \                /   \
 3     5        3     5              2     5
/ \            / \  /              / \  /
4   8          4   8 2            4   8 3

삭제 — pop()

루트 제거       마지막 원소를 루트로    자식과 비교하며 아래로 내려감 (heapify-down)
    1              8                      2
  /   \          /   \                  /   \
 2     5        2     5                3     5
/ \  /         / \                   / \
4   8 3        4   3                 4   8

3. 핵심 포인트 2가지

힙은 완전 이진 트리라 배열로 구현한다

트리 구조지만 포인터 없이 1차원 배열 인덱스로 부모/자식 관계를 표현한다.

인덱스 1부터 시작할 때:
- 부모: i / 2
- 왼쪽 자식: i * 2
- 오른쪽 자식: i * 2 + 1

Java PriorityQueue는 기본이 최소 힙이다

최대 힙이나 커스텀 정렬이 필요하면 Comparator를 넘겨야 한다.
Comparator에서 음수를 반환하면 앞에, 양수를 반환하면 뒤에 배치된다.

// a가 b보다 앞에 와야 하면 음수 반환
(a, b) -> a - b   // 오름차순 (최소 힙, 기본값)
(a, b) -> b - a   // 내림차순 (최대 힙)

4. 코드

Java PriorityQueue 기본 사용

// 최소 힙 (기본)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(3);
minHeap.offer(1);
minHeap.offer(2);
minHeap.peek();   // → 1 (꺼내지 않고 확인)
minHeap.poll();   // → 1 (꺼내기)

// 최대 힙
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());
maxHeap.offer(3);
maxHeap.offer(1);
maxHeap.offer(2);
maxHeap.poll();   // → 3

커스텀 Comparator — 절댓값 힙

// 절댓값 기준 오름차순, 절댓값 같으면 작은 수 우선
PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> {
    if (Math.abs(a) != Math.abs(b)) return Math.abs(a) - Math.abs(b);
    return a - b;
});

커스텀 Comparator — 객체 정렬

// [가중치, 노드번호] 배열을 가중치 오름차순으로 정렬
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{5, 1});
pq.offer(new int[]{2, 3});
pq.poll();  // → [2, 3]

최소 힙 + 최대 힙 — 중간값 구하기

// 최대 힙: 중간값 이하의 수들
PriorityQueue<Integer> lower = new PriorityQueue<>(Collections.reverseOrder());
// 최소 힙: 중간값 초과의 수들
PriorityQueue<Integer> upper = new PriorityQueue<>();

void add(int num) {
    // lower가 비어 있거나, num이 lower의 최댓값 이하면 lower에 삽입
    if (lower.isEmpty() || lower.peek() >= num) lower.offer(num);
    else upper.offer(num);

    // 크기 균형 맞추기 (lower가 upper보다 정확히 1개 많게 유지)
    if (lower.size() < upper.size()) lower.offer(upper.poll());
    if (lower.size() > upper.size() + 1) upper.offer(lower.poll());
}

int getMedian() {
    return lower.peek();  // 항상 중간값
}

직접 구현 — 최소 힙

class MinHeap {
    int[] heap = new int[100001];
    int size = 0;

    void push(int val) {
        heap[++size] = val;
        int i = size;
        // heapify-up: 부모보다 작으면 올라감
        while (i > 1 && heap[i] < heap[i / 2]) {
            int tmp = heap[i]; heap[i] = heap[i / 2]; heap[i / 2] = tmp;
            i /= 2;
        }
    }

    int pop() {
        int root = heap[1];
        heap[1] = heap[size--];
        int i = 1;
        // heapify-down: 자식 중 더 작은 쪽과 교환하며 내려감
        while (true) {
            int left = i * 2, right = i * 2 + 1, smallest = i;
            if (left <= size && heap[left] < heap[smallest]) smallest = left;
            if (right <= size && heap[right] < heap[smallest]) smallest = right;
            if (smallest == i) break;
            int tmp = heap[i]; heap[i] = heap[smallest]; heap[smallest] = tmp;
            i = smallest;
        }
        return root;
    }
}

5. 시간복잡도

연산	시간복잡도
peek (최솟값/최댓값 확인)	O(1)
offer (삽입)	O(log N)
poll (삭제)	O(log N)
N개 원소로 힙 구성 (heapify)	O(N)

삽입/삭제가 O(log N)이므로, N개의 원소를 정렬하면 O(N log N)이다.

6. 주의사항

Comparator에서 단순 뺄셈(a - b)은 오버플로우 위험이 있다. 값의 범위가 크면 Integer.compare(a, b)를 사용하라.
poll 전에 isEmpty() 확인을 습관화하라. 빈 힙에서 poll하면 null을 반환하고, int로 받으면 NullPointerException이 발생한다.
PriorityQueue는 전체 정렬이 보장되지 않는다. poll할 때만 우선순위가 보장되며, 내부 배열을 그대로 출력하면 정렬된 결과가 아니다.
같은 값이 여러 개 있어도 중복 삽입이 가능하다. Set과 달리 중복을 허용하므로 주의가 필요한 문제에서는 별도로 처리해야 한다.
직접 구현 시 인덱스를 1부터 시작하는 것이 부모/자식 계산이 편하다. 0부터 시작하면 (i-1)/2, 2*i+1, 2*i+2로 공식이 복잡해진다.