View

CS/자료구조

자료구조: Heap(= 우선순위 큐)

명이나물 라이브러리 2026. 5. 26. 14:53

Heap 정리, 우선순위 큐를 이해하기 위한 자료구조

자료구조에서 Stack, Queue, Deque를 정리한 뒤, 이번에는 Heap에 대해 공부했다.

처음에는 Heap이라는 이름만 보고 메모리 영역의 Heap을 떠올렸는데, 코딩테스트에서 말하는 Heap은 보통 우선순위가 높은 데이터를 빠르게 꺼내기 위한 자료구조를 의미한다.

Java에서는 Heap을 직접 구현하기보다는 보통 PriorityQueue를 사용한다.

1. Heap이란?

Heap은 최댓값 또는 최솟값을 빠르게 찾기 위한 완전 이진 트리 기반 자료구조이다.

코딩테스트에서는 보통 다음 상황에서 사용한다.

상황	사용하는 자료구조
가장 작은 값을 계속 꺼내야 한다	최소 힙
가장 큰 값을 계속 꺼내야 한다	최대 힙
우선순위가 높은 작업부터 처리해야 한다	우선순위 큐
매번 정렬하지 않고 최솟값/최댓값을 관리해야 한다	Heap

핵심은 이것이다.

Heap은 매번 전체 정렬하지 않고도 최솟값 또는 최댓값을 빠르게 꺼낼 수 있다.

2. Heap의 종류

Heap은 크게 두 가지로 나눌 수 있다.

종류	특징	루트에 있는 값
최소 힙	부모 노드가 자식 노드보다 작거나 같다	가장 작은 값
최대 힙	부모 노드가 자식 노드보다 크거나 같다	가장 큰 값

최소 힙

최소 힙은 가장 작은 값이 위에 있는 구조이다.

가장 위에 있는 값인 1이 가장 작다.

Java의 PriorityQueue는 기본적으로 최소 힙이다.

최대 힙

최대 힙은 가장 큰 값이 위에 있는 구조이다.

가장 위에 있는 값인 9가 가장 크다.

Java에서 최대 힙을 만들려면 Collections.reverseOrder()나 Comparator를 사용해야 한다.

3. Heap과 정렬의 차이

처음에는 “최솟값을 꺼낼 거면 그냥 정렬하면 되는 거 아닌가?”라는 생각이 들었다.

하지만 매번 값이 추가되고, 그때마다 최솟값이나 최댓값을 꺼내야 한다면 매번 정렬하는 것은 비효율적이다.

방식	특징
매번 정렬	구현은 쉽지만 반복적으로 정렬하면 비효율적
Heap 사용	값 추가/삭제가 발생해도 우선순위 유지 가능

예를 들어 다음과 같은 작업을 계속 반복해야 한다고 하자.

1. 값 추가
2. 가장 작은 값 꺼내기
3. 다시 값 추가
4. 다시 가장 작은 값 꺼내기

이런 경우에는 매번 정렬하기보다 Heap을 사용하는 것이 적합하다.

4. Heap의 시간복잡도

Heap에서 자주 사용하는 연산의 시간복잡도는 다음과 같다.

연산	시간복잡도
값 추가	`O(log N)`
최솟값/최댓값 꺼내기	`O(log N)`
최솟값/최댓값 확인	`O(1)`

전체를 정렬하면 보통 O(N log N)이 걸리지만, Heap은 매번 필요한 값만 빠르게 꺼낼 수 있다.

5. Java에서 Heap 사용하기

Java에서는 Heap을 직접 구현하지 않고 보통 PriorityQueue를 사용한다.

import java.util.*;

PriorityQueue<Integer> pq = new PriorityQueue<>();

PriorityQueue는 기본적으로 작은 값이 먼저 나오는 최소 힙이다.

6. 최소 힙 사용하기

import java.util.*;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        pq.offer(5);
        pq.offer(1);
        pq.offer(3);

        System.out.println(pq.poll()); // 1
        System.out.println(pq.poll()); // 3
        System.out.println(pq.poll()); // 5
    }
}

값을 넣은 순서는 5, 1, 3이지만, 꺼낼 때는 작은 값부터 나온다.

offer(5)
offer(1)
offer(3)

poll() → 1
poll() → 3
poll() → 5

7. PriorityQueue 주요 메서드

메서드	의미
`offer()`	값 넣기
`poll()`	우선순위가 가장 높은 값 꺼내기
`peek()`	우선순위가 가장 높은 값 확인
`isEmpty()`	비어 있는지 확인
`size()`	크기 확인

여기서 Java 기본 PriorityQueue에서 우선순위가 높다는 것은 값이 작다는 의미이다.

8. 최대 힙 사용하기

Java의 PriorityQueue는 기본적으로 최소 힙이다.
따라서 가장 큰 값을 먼저 꺼내고 싶다면 최대 힙으로 만들어야 한다.

방법 1. Collections.reverseOrder() 사용

PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

pq.offer(5);
pq.offer(1);
pq.offer(3);

System.out.println(pq.poll()); // 5
System.out.println(pq.poll()); // 3
System.out.println(pq.poll()); // 1

방법 2. Comparator 사용

PriorityQueue<Integer> pq =
        new PriorityQueue<>((a, b) -> Integer.compare(b, a));

이렇게 하면 큰 값이 먼저 나오게 된다.

PriorityQueue<Integer> pq =
        new PriorityQueue<>((a, b) -> Integer.compare(b, a));

pq.offer(5);
pq.offer(1);
pq.offer(3);

System.out.println(pq.poll()); // 5
System.out.println(pq.poll()); // 3
System.out.println(pq.poll()); // 1

여기서 주의할 점은 아래처럼 작성하지 않는 것이다.

(a, b) -> b - a

값의 범위가 크면 오버플로우가 발생할 수 있으므로 Integer.compare()를 사용하는 것이 안전하다.

9. 배열을 PriorityQueue에 넣기

코딩테스트에서는 숫자 하나만 우선순위 큐에 넣는 경우보다, 여러 정보를 함께 저장해야 하는 경우가 많다.

예를 들어 작업 정보를 다음처럼 저장한다고 하자.

[요청 시간, 소요 시간]

소요 시간이 짧은 작업부터 꺼내고 싶다면 두 번째 값 기준으로 정렬하면 된다.

PriorityQueue<int[]> pq = new PriorityQueue<>(
    (a, b) -> Integer.compare(a[1], b[1])
);

예시 코드:

import java.util.*;

public class Main {
    public static void main(String[] args) {
        PriorityQueue<int[]> pq = new PriorityQueue<>(
            (a, b) -> Integer.compare(a[1], b[1])
        );

        pq.offer(new int[]{0, 3});
        pq.offer(new int[]{1, 9});
        pq.offer(new int[]{2, 6});

        System.out.println(Arrays.toString(pq.poll())); // [0, 3]
        System.out.println(Arrays.toString(pq.poll())); // [2, 6]
        System.out.println(Arrays.toString(pq.poll())); // [1, 9]
    }
}

꺼내는 순서는 두 번째 값 기준이다.

값	기준값
`[0, 3]`	3
`[1, 9]`	9
`[2, 6]`	6

따라서 결과는 다음 순서로 나온다.

[0, 3] → [2, 6] → [1, 9]

10. 객체를 PriorityQueue에 넣기

배열 대신 클래스를 만들어 사용할 수도 있다.

class Job {
    int requestTime;
    int duration;

    Job(int requestTime, int duration) {
        this.requestTime = requestTime;
        this.duration = duration;
    }
}

소요 시간이 짧은 작업부터 꺼내려면 다음처럼 작성한다.

PriorityQueue<Job> pq = new PriorityQueue<>(
    (a, b) -> Integer.compare(a.duration, b.duration)
);

예시:

PriorityQueue<Job> pq = new PriorityQueue<>(
    (a, b) -> Integer.compare(a.duration, b.duration)
);

pq.offer(new Job(0, 3));
pq.offer(new Job(1, 9));
pq.offer(new Job(2, 6));

System.out.println(pq.poll().duration); // 3
System.out.println(pq.poll().duration); // 6
System.out.println(pq.poll().duration); // 9

객체를 사용하면 int[]보다 의미가 명확해진다는 장점이 있다.

11. Heap을 떠올릴 문제 유형

Heap은 “매번 가장 작은 값 또는 가장 큰 값을 꺼내야 하는 문제”에서 자주 등장한다.

문제 유형	Heap을 쓰는 이유
더 맵게	가장 작은 음식 2개를 계속 꺼내야 함
디스크 컨트롤러	현재 가능한 작업 중 소요 시간이 짧은 작업부터 처리
이중우선순위큐	최솟값과 최댓값 관리
다익스트라	현재 비용이 가장 작은 노드부터 탐색
Top K 문제	상위 K개 값 관리

12. Heap 문제를 볼 때 체크할 질문

Heap 문제인지 판단할 때는 아래 질문을 해보면 좋다.

체크 질문	Heap 가능성
매번 최솟값이 필요한가?	높음
매번 최댓값이 필요한가?	높음
값이 계속 추가되거나 삭제되는가?	높음
매번 정렬하면 비효율적인가?	높음
우선순위가 높은 작업부터 처리해야 하는가?	높음

문제에서 이런 표현이 나오면 Heap을 떠올려볼 수 있다.

가장 작은 값 두 개
가장 큰 값
우선순위가 높은 작업
소요 시간이 짧은 작업
최소 비용
상위 K개

13. PriorityQueue 사용 시 주의할 점

1. 전체가 정렬되어 있는 것은 아니다

PriorityQueue는 내부적으로 모든 값이 완전히 정렬된 상태는 아니다.
다만 poll()을 했을 때 우선순위가 가장 높은 값이 나온다.

즉, 아래처럼 출력하면 정렬된 것처럼 보이지 않을 수 있다.

System.out.println(pq);

정렬된 순서로 확인하고 싶다면 poll()로 하나씩 꺼내야 한다.

2. 중간 값을 바로 찾는 용도는 아니다

Heap은 최솟값이나 최댓값을 빠르게 꺼내는 데 좋다.
하지만 중간값을 바로 찾거나, 특정 값을 빠르게 검색하는 용도에는 적합하지 않다.

필요한 작업	적합한 자료구조
최솟값/최댓값 꺼내기	PriorityQueue
특정 값 존재 여부 확인	HashSet
key-value 매핑	HashMap
정렬된 전체 순회	정렬된 배열/List

3. Comparator에서 뺄셈 비교 주의

아래처럼 작성할 수는 있지만:

PriorityQueue<Integer> pq = new PriorityQueue<>((a, b) -> b - a);

값이 크면 오버플로우가 날 수 있다.

따라서 아래처럼 작성하는 것이 더 안전하다.

PriorityQueue<Integer> pq =
        new PriorityQueue<>((a, b) -> Integer.compare(b, a));

14. Heap 정리표

구분	내용
Heap	최솟값 또는 최댓값을 빠르게 찾기 위한 자료구조
최소 힙	가장 작은 값이 먼저 나옴
최대 힙	가장 큰 값이 먼저 나옴
Java 기본	`PriorityQueue`는 기본적으로 최소 힙
값 추가	`offer()`
값 꺼내기	`poll()`
값 확인	`peek()`
추가/삭제 시간복잡도	`O(log N)`
확인 시간복잡도	`O(1)`

15. 내가 이해한 Heap 핵심

이번에 Heap을 공부하면서 가장 중요하게 느낀 점은, Heap은 단순한 정렬이 아니라는 것이다.

정렬은 전체 데이터를 순서대로 배치하는 것이고,
Heap은 필요할 때마다 가장 우선순위가 높은 값만 빠르게 꺼내는 구조에 가깝다.

정렬 = 전체를 줄 세우기
Heap = 가장 급한 것부터 꺼내기

그래서 값이 계속 추가되고, 그때마다 최솟값이나 최댓값을 꺼내야 한다면 Heap을 떠올리면 된다.

마무리

Heap은 코딩테스트에서 PriorityQueue로 자주 사용된다.

특히 다음과 같은 문장을 만나면 Heap을 먼저 의심해볼 수 있다.

가장 작은 값부터 처리한다.
가장 큰 값부터 처리한다.
우선순위가 높은 작업부터 처리한다.
최솟값을 계속 꺼내야 한다.
최댓값을 계속 꺼내야 한다.

Java에서는 기본적으로 최소 힙이다.

PriorityQueue<Integer> pq = new PriorityQueue<>();

최대 힙이 필요하면 다음처럼 작성한다.

PriorityQueue<Integer> pq =
        new PriorityQueue<>(Collections.reverseOrder());

또는:

PriorityQueue<Integer> pq =
        new PriorityQueue<>((a, b) -> Integer.compare(b, a));

이번 Heap 공부를 정리하면 이렇게 기억하면 될 것 같다.

매번 최솟값/최댓값이 필요하면 Heap
Java에서는 PriorityQueue
기본은 최소 힙
최대 힙은 reverseOrder 또는 Comparator
배열/객체도 Comparator로 기준을 정할 수 있음

Heap 개념을 바탕으로 프로그래머스의 더 맵게, 디스크 컨트롤러, 이중우선순위큐 같은 문제를 풀어보면 좋을 것 같다.

저작자표시 (새창열림)

'CS > 자료구조' 카테고리의 다른 글

자료구조: Stack, Queue, Deque, PriorityQueue (0)	2026.05.26

Share Link

Facebook
Twitter

일	월	화	수	목	금	토
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

명이나물 라이브러리