[알고리즘] 21. 힙(Heap)

지난 글에서는 우선순위 큐(PriorityQueue)에 대해 정리했습니다. 이번 글에서는 PriorityQueue의 내부 동작과 깊게 연결된 자료구조인 힙(Heap)에 대해 알아보겠습니다.

힙은 최솟값이나 최댓값을 빠르게 찾기 위해 사용하는 자료구조입니다. 알고리즘 문제에서는 직접 힙을 구현하는 경우도 있지만, Java에서는 보통 PriorityQueue를 통해 힙 구조를 사용합니다.

힙은 부모와 자식 사이의 우선순위 관계를 유지하는 완전 이진 트리 기반 자료구조입니다.

1. 힙이란?

힙은 여러 데이터 중에서 가장 작은 값이나 가장 큰 값을 빠르게 꺼내기 위해 사용하는 자료구조입니다.

예를 들어 숫자들이 다음과 같이 있다고 생각해보겠습니다.

30, 10, 40, 20, 50

이 중 가장 작은 값은 10입니다. 배열에서 최솟값을 찾으려면 모든 값을 확인해야 할 수 있지만, 힙을 사용하면 가장 우선순위가 높은 값을 빠르게 확인할 수 있습니다.

힙은 보통 아래 상황에서 사용됩니다.

최솟값을 반복해서 꺼내야 할 때
최댓값을 반복해서 꺼내야 할 때
우선순위가 높은 작업부터 처리해야 할 때
PriorityQueue의 동작 원리를 이해해야 할 때
다익스트라 알고리즘처럼 최소 비용을 계속 선택해야 할 때

힙은 모든 값을 완전히 정렬하는 구조가 아니라, 가장 우선순위가 높은 값을 빠르게 꺼내기 위한 구조입니다.

2. 힙은 완전 이진 트리 구조입니다

힙은 완전 이진 트리 형태를 기반으로 합니다. 완전 이진 트리는 위에서 아래로, 왼쪽에서 오른쪽으로 노드가 채워지는 트리입니다.

위 구조는 위쪽부터 차례대로 채워져 있고, 마지막 줄도 왼쪽부터 채워져 있습니다. 이런 형태를 완전 이진 트리라고 합니다.

힙은 이 완전 이진 트리 구조를 사용하면서 부모와 자식 사이에 특정한 규칙을 유지합니다.

힙은 모양은 완전 이진 트리이고, 값은 부모와 자식의 우선순위 규칙을 따릅니다.

3. 최소 힙과 최대 힙

힙은 크게 최소 힙과 최대 힙으로 나눌 수 있습니다.

구분	규칙	먼저 나오는 값
최소 힙	부모 노드가 자식 노드보다 작거나 같음	가장 작은 값
최대 힙	부모 노드가 자식 노드보다 크거나 같음	가장 큰 값

Java의 PriorityQueue는 기본적으로 최소 힙입니다. 즉 가장 작은 값이 먼저 나옵니다.

최소 힙: 가장 작은 값이 루트에 있음
최대 힙: 가장 큰 값이 루트에 있음

여기서 루트는 트리의 가장 위에 있는 노드를 의미합니다.

4. 최소 힙 예시

최소 힙에서는 부모 노드가 자식 노드보다 작거나 같아야 합니다.

위 구조를 보면 부모가 자식보다 항상 작습니다.

10은 20보다 작다.
10은 30보다 작다.
20은 40보다 작다.
20은 50보다 작다.

따라서 가장 작은 값인 10이 루트에 위치합니다. 최소 힙에서는 루트 값을 꺼내면 현재 가장 작은 값을 얻을 수 있습니다.

최소 힙에서는 루트가 항상 가장 작은 값입니다.

5. 최대 힙 예시

최대 힙에서는 부모 노드가 자식 노드보다 크거나 같아야 합니다.

위 구조에서는 가장 큰 값인 50이 루트에 있습니다. 부모 노드가 자식 노드보다 항상 크기 때문에 최대 힙 조건을 만족합니다.

50은 40보다 크다.
50은 30보다 크다.
40은 10보다 크다.
40은 20보다 크다.

최대 힙에서는 루트 값을 꺼내면 현재 가장 큰 값을 얻을 수 있습니다.

최대 힙에서는 루트가 항상 가장 큰 값입니다.

6. 힙은 전체 정렬 상태가 아닙니다

힙을 처음 볼 때 가장 많이 헷갈리는 부분이 있습니다. 힙은 전체 데이터가 정렬된 구조가 아닙니다.

최소 힙에서 중요한 것은 부모가 자식보다 작거나 같다는 규칙입니다. 왼쪽 자식과 오른쪽 자식끼리의 순서는 반드시 정렬되어 있을 필요가 없습니다.

위 구조도 최소 힙이 될 수 있습니다. 루트 10은 30과 20보다 작고, 30은 50과 40보다 작습니다. 하지만 같은 레벨의 30과 20은 정렬되어 있지 않습니다.

즉 힙은 전체 정렬이 아니라 부모와 자식 사이의 우선순위 관계만 유지합니다.

힙은 정렬된 배열이 아니라, 최상단 값만 빠르게 찾을 수 있는 구조입니다.

7. 힙을 배열로 표현하기

힙은 트리 구조처럼 보이지만, 실제로는 배열로 표현할 수 있습니다. 완전 이진 트리이기 때문에 배열 인덱스를 이용해 부모와 자식의 위치를 계산할 수 있습니다.

위 힙을 배열로 표현하면 다음과 같습니다.

인덱스: 0   1   2   3   4
값:    10  20  30  40  50

배열의 0번 인덱스가 루트입니다. 그리고 각 노드의 왼쪽 자식과 오른쪽 자식 위치는 인덱스 계산으로 찾을 수 있습니다.

8. 부모와 자식 인덱스 공식

힙을 배열로 표현할 때 인덱스가 0부터 시작한다면 부모와 자식의 위치는 다음과 같이 계산할 수 있습니다.

구분	공식
왼쪽 자식	index * 2 + 1
오른쪽 자식	index * 2 + 2
부모	(index - 1) / 2

예를 들어 인덱스 1에 있는 값 20의 자식은 다음 위치에 있습니다.

왼쪽 자식: 1 * 2 + 1 = 3
오른쪽 자식: 1 * 2 + 2 = 4

실제로 배열에서 3번 인덱스는 40, 4번 인덱스는 50입니다.

인덱스: 0   1   2   3   4
값:    10  20  30  40  50

힙은 완전 이진 트리라서 배열 인덱스만으로 부모와 자식 위치를 계산할 수 있습니다.

9. 힙에 값 추가하기

힙에 새로운 값을 추가할 때는 먼저 마지막 위치에 값을 넣습니다. 그다음 부모와 비교하면서 힙의 규칙이 깨졌다면 위로 올립니다.

최소 힙에 5를 추가한다고 생각해보겠습니다.

5는 부모인 20보다 작습니다. 최소 힙에서는 부모가 자식보다 작아야 하므로 위치를 바꿔야 합니다.

이제 5의 부모는 10입니다. 5는 10보다 작기 때문에 다시 위치를 바꿉니다.

이렇게 새로 추가한 값이 부모와 비교하면서 위로 올라가는 과정을 상향 이동이라고 볼 수 있습니다.

힙에 값을 추가하면 마지막에 넣고, 부모와 비교하며 필요한 만큼 위로 올립니다.

10. 힙에서 값 꺼내기

힙에서 값을 꺼낼 때는 루트 값을 제거합니다. 최소 힙에서는 루트가 가장 작은 값이고, 최대 힙에서는 루트가 가장 큰 값입니다.

최소 힙에서 루트 10을 꺼내는 상황을 보겠습니다.

루트 10을 제거한 뒤에는 마지막 값을 루트 자리로 올립니다.

이제 최소 힙 규칙이 깨졌습니다. 50은 자식인 20과 30보다 큽니다. 따라서 더 작은 자식과 위치를 바꿉니다.

50은 아직 자식 40보다 크므로 다시 위치를 바꿉니다.

이렇게 루트로 올라온 값을 자식과 비교하면서 아래로 내려보내는 과정을 하향 이동이라고 볼 수 있습니다.

힙에서 값을 꺼내면 마지막 값을 루트로 올리고, 자식과 비교하며 아래로 내립니다.

11. Java PriorityQueue와 힙

Java에서 직접 힙을 구현하지 않아도 PriorityQueue를 사용하면 힙 기능을 사용할 수 있습니다. PriorityQueue는 내부적으로 힙 구조를 이용해 우선순위가 높은 값을 빠르게 꺼낼 수 있게 해줍니다.

import java.util.PriorityQueue;

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

pq.offer(30);
pq.offer(10);
pq.offer(20);

System.out.println(pq.poll());
System.out.println(pq.poll());
System.out.println(pq.poll());

출력 결과는 다음과 같습니다.

10
20
30

PriorityQueue는 내부적으로 최소 힙처럼 동작하기 때문에 작은 값부터 나옵니다.

최대 힙처럼 사용하고 싶다면 reverseOrder()를 사용할 수 있습니다.

import java.util.Collections;
import java.util.PriorityQueue;

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

pq.offer(30);
pq.offer(10);
pq.offer(20);

System.out.println(pq.poll());
System.out.println(pq.poll());
System.out.println(pq.poll());

출력 결과는 다음과 같습니다.

30
20
10

12. 힙의 시간복잡도

힙은 가장 위에 있는 값을 확인하는 것은 빠르지만, 값을 넣거나 꺼낼 때는 힙 구조를 다시 맞춰야 합니다.

연산	시간복잡도	설명
최상단 값 확인	O(1)	루트 값을 바로 확인
값 추가	O(log N)	부모와 비교하며 위로 이동
값 삭제	O(log N)	자식과 비교하며 아래로 이동

힙의 높이는 데이터 개수 N에 대해 log N 수준입니다. 그래서 값을 넣거나 꺼낼 때 O(log N)이 걸립니다.

힙은 최상단 확인은 O(1), 삽입과 삭제는 O(log N)입니다.

13. 힙이 사용되는 대표 상황

힙은 우선순위가 중요한 문제에서 자주 사용됩니다.

상황	이유
최솟값 반복 추출	최소 힙으로 빠르게 처리 가능
최댓값 반복 추출	최대 힙으로 빠르게 처리 가능
우선순위 작업 처리	중요도가 높은 작업부터 처리 가능
다익스트라 알고리즘	현재 비용이 가장 작은 노드를 먼저 선택
카드 정렬 / 파일 합치기	가장 작은 두 값을 반복해서 합침

문제를 보고 “가장 작은 값” 또는 “가장 큰 값”을 계속 꺼내야 한다면 힙을 떠올리면 좋습니다.

14. 힙과 정렬의 차이

힙을 사용하면 값을 우선순위 순서대로 꺼낼 수 있기 때문에 정렬과 비슷해 보일 수 있습니다. 하지만 목적은 조금 다릅니다.

구분	정렬	힙
목적	전체 데이터를 순서대로 나열	우선순위가 높은 값 빠르게 꺼내기
상태	전체가 정렬됨	부모와 자식 관계만 유지
중간 삽입	정렬 상태 유지가 번거로움	삽입 후 힙 구조 조정 가능
대표 사용	전체 순서가 필요할 때	최솟값/최댓값을 반복해서 꺼낼 때

전체 결과를 한 번에 정렬해야 한다면 정렬을 사용하고, 계속 값이 추가되거나 가장 작은 값만 반복해서 꺼내야 한다면 힙이 더 적합할 수 있습니다.

힙은 전체 정렬보다 우선순위 값 추출에 초점이 맞춰진 자료구조입니다.

15. 힙에서 자주 하는 실수

힙을 공부할 때는 아래 실수를 자주 합니다.

힙이 전체 정렬된 상태라고 생각하는 경우
최소 힙과 최대 힙의 기준을 헷갈리는 경우
PriorityQueue 출력 결과가 정렬되어 있지 않다고 착각하는 경우
부모와 자식 인덱스 공식을 잘못 사용하는 경우
값을 꺼낸 뒤 힙 구조를 다시 맞춰야 한다는 점을 놓치는 경우
최댓값이 필요한데 Java 기본 PriorityQueue를 그대로 사용하는 경우

특히 PriorityQueue를 출력했을 때 정렬된 것처럼 보이지 않아도 이상한 것이 아닙니다. 중요한 것은 poll()로 꺼낼 때 우선순위 순서대로 나온다는 점입니다.

힙은 출력 모양보다 꺼내는 순서가 중요합니다.

16. 정리

이번 글에서는 힙에 대해 정리했습니다.

힙은 최솟값이나 최댓값을 빠르게 꺼내기 위한 자료구조이다.
힙은 완전 이진 트리 구조를 기반으로 한다.
최소 힙은 부모가 자식보다 작거나 같고, 가장 작은 값이 루트에 있다.
최대 힙은 부모가 자식보다 크거나 같고, 가장 큰 값이 루트에 있다.
힙은 전체 정렬 상태가 아니라 부모와 자식 사이의 관계만 유지한다.
힙은 배열로 표현할 수 있고, 인덱스 공식으로 부모와 자식을 찾을 수 있다.
값 추가와 삭제는 O(log N), 최상단 확인은 O(1)이다.
Java PriorityQueue는 내부적으로 힙 구조를 이용한다.

힙은 PriorityQueue를 제대로 이해하기 위한 핵심 자료구조입니다. 직접 구현하지 않더라도 최소 힙, 최대 힙, 부모와 자식 관계를 이해하면 우선순위 큐 문제를 훨씬 안정적으로 풀 수 있습니다.

힙의 핵심은 전체를 정렬하는 것이 아니라, 가장 우선순위가 높은 값을 빠르게 꺼내는 것입니다.

다음 글 예고

다음 글에서는 트리 기초에 대해 알아보겠습니다.

트리의 개념, 루트와 부모·자식 노드, 깊이와 높이, 이진 트리의 기본 구조를 예제로 정리해보겠습니다.

'Problem Solving > Algorithm' 카테고리의 다른 글

[알고리즘] 23. 그래프 기초 (0)	2026.07.06
[알고리즘] 22. 트리 기초 (0)	2026.07.05
[알고리즘] 20. 우선순위 큐(PriorityQueue) (0)	2026.07.03
[알고리즘] 19. 해시셋(HashSet) (0)	2026.07.02
[알고리즘] 18. 해시맵(HashMap) (1)	2026.07.01