힙(Heap) / 우선순위 큐(Priority Queue)
1. 힙(Heap)이란?
이번에는 트리 자료구조에서 자연스럽게 이어지는 힙(Heap)과 우선순위 큐(Priority Queue)에 대해 학습했다.
힙은 완전 이진 트리(Complete Binary Tree)의 형태를 가지면서, 부모 노드와 자식 노드 사이에 특정한 우선순위 관계를 유지하는 자료구조이다.
힙은 크게 두 종류로 나눌 수 있다.
- Min Heap
- Max Heap
여기서 중요한 점은 힙을 단순히 값이 정렬되어 있는 트리라고 생각하면 안 된다는 것이다.
예를 들어 Max Heap은 다음과 같은 형태를 가질 수 있다.
100
/ \
80 70
/ \ / \
50 60 40 30
Max Heap에서는 부모가 항상 자식보다 크거나 같아야 한다.
부모 >= 자식
하지만 같은 레벨에 있는 형제 노드까지 정렬되어 있어야 하는 것은 아니다.
따라서 힙은 전체 데이터가 정렬되어 있는 트리가 아니라, 부모와 자식 사이의 우선순위 관계를 유지하는 자료구조라고 이해하는 것이 중요하다.
2. 완전 이진 트리
힙을 이해하기 위해서는 먼저 완전 이진 트리(Complete Binary Tree)의 개념을 이해해야 한다.
완전 이진 트리는 마지막 레벨을 제외한 모든 레벨이 가득 차 있고, 마지막 레벨은 왼쪽부터 차례대로 채워지는 형태의 이진 트리이다.
예를 들어 다음과 같은 트리는 완전 이진 트리이다.
A
/ \
B C
/ \ /
D E F
반면 다음과 같은 형태는 완전 이진 트리가 아니다.
A
/ \
B C
\
E
힙은 이러한 완전 이진 트리 구조를 사용하기 때문에 배열로 효율적으로 표현할 수 있다.
3. 힙을 배열로 표현하기
힙에서 중요한 특징 중 하나는 트리 형태로 보이지만 실제 구현에서는 배열 하나만으로 표현할 수 있다는 것이다.
다음과 같은 Max Heap이 있다고 생각해 보았다.
100
/ \
80 70
/ \ / \
50 60 40 30
이를 배열로 표현하면 다음과 같다.
[100, 80, 70, 50, 60, 40, 30]
0부터 시작하는 배열의 인덱스를 기준으로 현재 노드의 인덱스를 i라고 하면 부모와 자식의 위치를 계산할 수 있다.
부모 = (i - 1) / 2
왼쪽 자식 = 2 * i + 1
오른쪽 자식 = 2 * i + 2
예를 들어 80은 인덱스 1에 있다.
부모는 다음과 같이 계산할 수 있다.
(1 - 1) / 2
= 0
따라서 부모는 인덱스 0의 100이다.
왼쪽 자식은:
2 * 1 + 1
= 3
이므로 50이다.
오른쪽 자식은:
2 * 1 + 2
= 4
이므로 60이다.
전체적으로 보면 다음과 같은 관계가 된다.
100 [0]
/ \
80 [1] 70 [2]
/ \ / \
50[3] 60[4] 40[5] 30[6]
따라서 힙은 트리의 구조를 가지지만, 완전 이진 트리의 특성 때문에 배열의 인덱스 계산만으로 부모와 자식의 위치를 알 수 있다.
4. Min Heap
Min Heap에서는 부모 노드의 값이 자식 노드보다 작거나 같아야 한다.
10
/ \
20 30
/ \ / \
40 50 60 70
각 부모와 자식의 관계는 다음과 같다.
10 <= 20
10 <= 30
20 <= 40
20 <= 50
30 <= 60
30 <= 70
따라서 Min Heap에서는 가장 작은 값이 항상 루트에 존재한다.
즉,
Root = 최솟값
이 된다.
따라서 가장 작은 값을 빠르게 확인하거나 꺼내야 하는 상황에서 Min Heap을 사용할 수 있다.
5. Max Heap
Max Heap에서는 부모 노드의 값이 자식 노드보다 크거나 같아야 한다.
100
/ \
80 70
/ \ / \
50 60 40 30
각 부모와 자식의 관계를 보면:
100 >= 80
100 >= 70
80 >= 50
80 >= 60
70 >= 40
70 >= 30
이 조건을 만족한다.
따라서 Max Heap에서는 가장 큰 값이 항상 루트에 존재한다.
Root = 최댓값
가 된다.
6. Min Heap과 Max Heap 비교
종류부모와 자식의 관계Root
| Min Heap | 부모 ≤ 자식 | 최솟값 |
| Max Heap | 부모 ≥ 자식 | 최댓값 |
정리하면 다음과 같다.
Min Heap
→ 가장 작은 값이 위로 올라감
Max Heap
→ 가장 큰 값이 위로 올라감
7. Heapify
Heapify는 힙의 조건을 만족하도록 노드의 위치를 조정하는 과정이다.
예를 들어 Max Heap에서 다음과 같은 상태가 있다고 생각해 보았다.
50
/ \
80 70
Max Heap에서는 부모가 자식보다 커야 하는데:
50 < 80
이므로 힙의 조건을 만족하지 않는다.
따라서 50과 80의 위치를 바꾼다.
80
/ \
50 70
이제 부모인 80이 자식보다 크기 때문에 Max Heap 조건을 만족한다.
이처럼 힙의 조건을 다시 만족하도록 노드들을 조정하는 과정을 Heapify라고 한다.
8. Heapify의 기본 과정
Max Heap을 기준으로 생각하면 Heapify는 다음과 같은 방식으로 진행된다.
- 현재 노드를 확인한다.
- 왼쪽 자식을 확인한다.
- 오른쪽 자식을 확인한다.
- 현재 노드와 두 자식 중 가장 큰 값을 찾는다.
- 자식이 현재 노드보다 크다면 두 값을 교환한다.
- 교환한 위치에서도 다시 Heapify를 진행한다.
예를 들어:
50
/ \
80 70
에서 가장 큰 값은 80이다.
따라서:
80
/ \
50 70
으로 바꾼다.
이 과정을 통해 힙의 조건을 만족하게 된다.
Heapify는 트리의 높이만큼 내려가면서 확인할 수 있기 때문에 일반적으로:
O(log N)
의 시간 복잡도를 가진다.
9. Insert
힙에 새로운 값을 추가하는 과정이다.
Max Heap에 90이라는 값을 추가한다고 생각해 보았다.
기존 힙은 다음과 같다.
100
/ \
80 70
/ \ / \
50 60 40 30
새로운 값은 완전 이진 트리의 구조를 유지하기 위해 가장 마지막 위치에 추가한다.
100
/ \
80 70
/ \ / \
50 60 40 30
/
90
하지만 90은 부모인 50보다 크다.
90 > 50
따라서 Max Heap의 조건을 만족하지 않는다.
부모와 위치를 바꾼다.
100
/ \
80 70
/ \ / \
90 60 40 30
/
50
이번에는 90이 부모인 80보다 크다.
90 > 80
따라서 다시 교환한다.
100
/ \
90 70
/ \ / \
80 60 40 30
/
50
이제:
100 >= 90
90 >= 80
이므로 Max Heap 조건을 만족한다.
이처럼 새로운 값을 마지막에 삽입한 후 부모와 비교하면서 위쪽으로 이동시키는 과정을 Sift Up, Bubble Up, Up-Heap이라고 한다.
Insert의 시간 복잡도는:
O(log N)
이다.
10. Delete
힙에서 Delete를 할 때 중요한 점은 일반적으로 루트 노드를 제거한다는 것이다.
Max Heap에서는 최댓값을 제거하고, Min Heap에서는 최솟값을 제거한다.
예를 들어 Max Heap에서 다음과 같은 구조가 있다.
100
/ \
80 70
/ \ / \
50 60 40 30
루트인 100을 제거한다.
그런데 단순히 100만 삭제하면 완전 이진 트리의 구조가 깨질 수 있다.
따라서 일반적으로 가장 마지막에 있는 노드 30을 루트로 이동시킨다.
30
/ \
80 70
/ \ /
50 60 40
그러나:
30 < 80
30 < 70
이므로 Max Heap 조건을 만족하지 않는다.
따라서 30을 더 큰 자식인 80과 교환한다.
80
/ \
30 70
/ \ /
50 60 40
다시 확인하면:
30 < 50
30 < 60
이므로 또 조건을 만족하지 않는다.
이번에는 더 큰 자식인 60과 교환한다.
80
/ \
60 70
/ \ /
50 30 40
이제 Max Heap 조건을 만족한다.
이처럼 루트를 제거하고 마지막 노드를 위로 이동시킨 다음, 아래쪽으로 내려가면서 힙을 다시 정리하는 과정을 Sift Down, Bubble Down, Down-Heap이라고 한다.
Delete의 시간 복잡도 역시:
O(log N)
이다.
11. Insert와 Delete 비교
Insert와 Delete는 이동 방향이 반대라는 점을 기억하면 이해하기 쉽다.
Insert
새로운 값 삽입
↓
마지막 위치에 추가
↓
부모와 비교
↓
필요하면 위로 이동
즉:
Insert
→ Sift Up
→ O(log N)
이다.
Delete
Root 제거
↓
마지막 노드를 Root로 이동
↓
자식과 비교
↓
필요하면 아래로 이동
즉:
Delete
→ Sift Down
→ O(log N)
이다.
결국:
Insert → 위로
Delete → 아래로
라고 정리할 수 있다.
12. 힙의 시간 복잡도
힙의 주요 연산을 정리하면 다음과 같다.
연산시간 복잡도
| 최솟값/최댓값 확인 | O(1) |
| Insert | O(log N) |
| Root Delete | O(log N) |
| Heapify | O(log N) |
| 전체 Heap 구성 | O(N) |
특히 기억해야 할 부분은:
Root 확인 → O(1)
Insert → O(log N)
Root Delete → O(log N)
이다.
힙의 높이가 O(log N)이기 때문에 Insert와 Delete가 O(log N)으로 처리될 수 있다.
13. 힙은 일반적인 탐색에는 적합하지 않다
힙은 모든 데이터가 정렬되어 있는 구조가 아니다.
예를 들어 Max Heap이:
100
/ \
80 70
/ \ / \
50 60 40 30
이라고 해보자.
여기서 60이라는 값을 찾는다고 하면, 힙에서는 특정 값의 위치를 빠르게 알 수 있는 규칙이 없다.
힙이 보장하는 것은:
부모와 자식의 우선순위 관계
이지 전체 데이터의 정렬 관계가 아니다.
따라서 힙은 특정 값을 찾는 용도보다는 최솟값이나 최댓값처럼 우선순위가 높은 데이터를 빠르게 처리하는 용도에 적합하다.
14. 우선순위 큐(Priority Queue)
일반적인 Queue는:
FIFO
First In First Out
방식이다.
즉 먼저 들어온 데이터가 먼저 나간다.
예를 들어:
A → B → C
순서로 들어왔다면:
A
B
C
순서로 나간다.
하지만 Priority Queue는 들어온 순서가 아니라 우선순위가 높은 데이터를 먼저 처리한다.
예를 들어:
A : 우선순위 3
B : 우선순위 10
C : 우선순위 5
라면 우선순위가 높은 순서대로:
B
C
A
와 같이 처리할 수 있다.
즉 Priority Queue의 핵심은:
먼저 들어온 데이터
가 아니라:
우선순위가 높은 데이터
를 먼저 처리한다는 것이다.
15. Heap과 Priority Queue의 관계
이번 학습에서 가장 중요하게 이해해야 할 부분 중 하나이다.
Priority Queue는 우선순위가 높은 데이터를 먼저 처리하는 추상적인 자료구조 개념이고, Heap은 Priority Queue를 효율적으로 구현할 수 있는 대표적인 자료구조이다.
관계를 정리하면:
Priority Queue
↑
구현 방법
↑
Heap
이라고 볼 수 있다.
Max Heap을 사용하면:
가장 큰 값
→ 가장 높은 우선순위
로 처리할 수 있다.
Min Heap을 사용하면:
가장 작은 값
→ 가장 높은 우선순위
로 처리할 수 있다.
따라서:
Max Heap
→ 최댓값 우선 Priority Queue
Min Heap
→ 최솟값 우선 Priority Queue
로 연결해서 이해할 수 있다.
16. C++의 Priority Queue
C++에서는 STL을 통해 Priority Queue를 사용할 수 있다.
대표적으로:
std::priority_queue
가 있다.
기본적으로 std::priority_queue는 Max Heap 방식으로 동작한다.
std::priority_queue<int> pq;
pq.push(10);
pq.push(30);
pq.push(20);
std::cout << pq.top();
결과는:
30
이 된다.
가장 큰 값이 우선순위가 높기 때문이다.
현재 구조를 개념적으로 보면:
30
20
10
과 같은 우선순위로 처리된다.
17. Min Priority Queue
가장 작은 값을 먼저 처리하고 싶다면 Min Heap을 사용할 수 있다.
대표적으로 다음과 같은 형태를 사용할 수 있다.
std::priority_queue<int, std::vector<int>, std::greater<int>>
이 경우 가장 작은 값이 우선순위가 높아진다.
예를 들어:
10
20
30
순서로 처리할 수 있다.
따라서 C++에서는:
std::priority_queue
→ 기본적으로 Max Heap
std::priority_queue + std::greater
→ Min Heap
이라고 이해할 수 있다.
18. Priority Queue의 주요 연산
Priority Queue에서 자주 사용하는 연산은 다음과 같다.
push()
데이터를 삽입한다.
top()
현재 가장 높은 우선순위의 데이터를 확인한다.
pop()
현재 가장 높은 우선순위의 데이터를 제거한다.
시간 복잡도는 다음과 같다.
push → O(log N)
top → O(1)
pop → O(log N)
즉 가장 높은 우선순위의 데이터를 확인하는 것은 매우 빠르고, 데이터를 삽입하거나 제거할 때는 힙의 구조를 다시 정리하기 때문에 O(log N)이 걸린다.
19. Priority Queue의 활용
Priority Queue는 실제 프로그램에서 다양한 상황에 사용할 수 있다.
예를 들어 게임에서 여러 적을 관리한다고 생각해 보았다.
적 A : 거리 100
적 B : 거리 20
적 C : 거리 50
가장 가까운 적을 먼저 처리하고 싶다면 Min Heap 기반 Priority Queue를 사용할 수 있다.
그 외에도:
퀘스트 우선순위
이벤트 우선순위
AI 행동 우선순위
작업 처리 순서
작업 스케줄링
경로 탐색
등 다양한 상황에서 사용할 수 있다.
특히 이후에 그래프 알고리즘을 공부하면서 Dijkstra 최단 경로 알고리즘 등을 학습하게 되면 Priority Queue가 중요한 역할을 한다는 것을 확인할 수 있다.
20. Heap Sort
Heap은 Priority Queue뿐만 아니라 Heap Sort와도 연결된다.
즉 이번 단계에서는 다음 두 가지 방향으로 연결해서 이해할 수 있다.
Heap
↓
Priority Queue
그리고:
Heap
↓
Heap Sort
이다.
Heap Sort는 Heap의 특성을 이용해서 데이터를 정렬하는 알고리즘이다.
21. Max Heap을 이용한 Heap Sort
예를 들어 다음 배열을 오름차순으로 정렬한다고 생각해 보았다.
[4, 10, 3, 5, 1]
먼저 배열을 Max Heap으로 만든다.
10
/ \
5 3
/ \
4 1
배열로 나타내면:
[10, 5, 3, 4, 1]
이제 Max Heap의 루트에는 가장 큰 값인 10이 존재한다.
따라서 10을 배열의 마지막 위치로 이동한다.
[1, 5, 3, 4, 10]
이제 10은 정렬이 끝난 영역으로 취급하고, 나머지 영역을 다시 Heapify한다.
[5, 4, 3, 1, 10]
다시 루트에 있는 가장 큰 값 5를 뒤쪽으로 이동한다.
[1, 4, 3, 5, 10]
그리고 다시 Heapify한다.
[4, 1, 3, 5, 10]
이 과정을 반복하면 최종적으로:
[1, 3, 4, 5, 10]
이라는 오름차순 배열이 만들어진다.
22. Heap Sort의 전체 과정
Heap Sort의 기본적인 흐름은 다음과 같다.
배열
↓
Heap 생성
↓
Root의 최댓값 확인
↓
최댓값을 배열의 뒤쪽으로 이동
↓
남은 영역 Heapify
↓
다시 최댓값을 뒤쪽으로 이동
↓
반복
↓
정렬 완료
즉 Max Heap에서는:
현재 가장 큰 값
→ Root
→ 배열의 마지막으로 이동
→ 남은 영역을 다시 Heapify
하는 과정을 반복한다.
23. Heap Sort의 시간 복잡도
Heap Sort의 시간 복잡도는:
O(N log N)
이다.
Heap을 구성하고, 이후 반복적으로 Heapify를 수행하기 때문이다.
특히 Heap Sort에서 중요한 특징은 최악의 경우에도 O(N log N)을 보장한다는 것이다.
퀵 정렬의 경우 평균적으로 O(N log N)이지만 피벗 선택 등에 따라 최악의 경우 O(N²)이 될 수 있다.
반면 Heap Sort는 일반적인 Heap Sort 구현에서:
최선 → O(N log N)
평균 → O(N log N)
최악 → O(N log N)
으로 볼 수 있다.
24. Heap Sort의 공간 복잡도
Heap Sort는 배열 내부에서 데이터를 이동시키면서 정렬할 수 있다.
따라서 별도의 큰 배열을 추가로 만들 필요가 없는 In-place 정렬 알고리즘으로 구현할 수 있다.
일반적인 In-place Heap Sort에서는 추가 공간을:
O(1)
수준으로 사용할 수 있다.
25. Heap Sort와 다른 정렬 알고리즘 비교
앞에서 공부한 정렬 알고리즘들과 비교해 보았다.
정렬평균 시간 복잡도최악 시간 복잡도특징
| 버블 정렬 | O(N²) | O(N²) | 구현이 단순하지만 느림 |
| 선택 정렬 | O(N²) | O(N²) | 구현이 단순함 |
| 삽입 정렬 | O(N²) | O(N²) | 거의 정렬된 데이터에서 유리 |
| 병합 정렬 | O(N log N) | O(N log N) | 안정적이며 추가 공간 필요 |
| 퀵 정렬 | O(N log N) | O(N²) | 평균적으로 빠름 |
| 힙 정렬 | O(N log N) | O(N log N) | 최악에도 일정하며 In-place 가능 |
Heap Sort는 최악의 경우에도 O(N log N)을 보장하고, In-place 방식으로 구현할 수 있다는 점이 중요한 특징이다.
26. Heap과 Binary Search Tree의 차이
둘 다 트리와 관련되어 있기 때문에 헷갈릴 수 있지만 목적이 다르다.
Max Heap은:
100
/ \
80 70
/ \
50 60
처럼 부모와 자식 사이의 관계를 보장한다.
부모 >= 자식
하지만 왼쪽 전체와 오른쪽 전체의 크기 관계까지 보장하지는 않는다.
반면 Binary Search Tree는:
50
/ \
30 70
/ \ / \
20 40 60 80
처럼:
왼쪽 < 부모 < 오른쪽
이라는 규칙을 가진다.
따라서:
Heap
→ 우선순위 처리에 적합
Binary Search Tree
→ 탐색에 적합
하다고 이해할 수 있다.
27. Heap에서 배운 핵심 개념
이번 단계에서 배운 개념을 정리하면 다음과 같다.
Heap
완전 이진 트리
+
부모와 자식 사이의 우선순위 관계
Min Heap
부모 <= 자식
→ Root = 최솟값
Max Heap
부모 >= 자식
→ Root = 최댓값
Heapify
힙의 조건을 만족하도록 노드의 위치를 조정하는 과정
Insert
마지막 위치에 삽입
→ Sift Up
→ O(log N)
Delete
Root 제거
→ 마지막 노드를 Root로 이동
→ Sift Down
→ O(log N)
Priority Queue
우선순위가 높은 데이터를 먼저 처리하는 자료구조
대표적인 구현 방법으로 Heap을 사용할 수 있다.
Heap Sort
Heap 생성
→ Root의 최댓값 또는 최솟값을 정렬 영역으로 이동
→ Heapify
→ 반복
→ O(N log N)
28. 전체 개념 연결
이번 단계의 전체적인 연결 관계는 다음과 같이 정리할 수 있다.
트리
↓
완전 이진 트리
↓
Heap
├── Min Heap
│ └── Root = 최솟값
│
└── Max Heap
└── Root = 최댓값
↓
Heapify
↓
Insert / Delete
↓
Priority Queue
↓
우선순위가 높은 데이터부터 처리
그리고 Heap은 정렬 알고리즘에도 연결된다.
Heap
↓
Heap Sort
↓
O(N log N)
결국 이번 단계에서는 단순히 Heap이라는 자료구조 하나를 배우는 것이 아니라,
Tree
↓
Complete Binary Tree
↓
Heap
↓
Priority Queue
↓
Heap Sort
로 이어지는 하나의 흐름을 이해하는 것이 중요했다.
29. 자료구조 전체 흐름에서 Heap의 위치
지금까지 학습한 자료구조를 연결해 보면 다음과 같이 정리할 수 있다.
Array
↓
인덱스를 이용한 빠른 접근
Linked List
↓
노드 간 연결을 이용한 데이터 관리
Stack
↓
LIFO
↓
마지막에 들어온 데이터부터 처리
Queue
↓
FIFO
↓
먼저 들어온 데이터부터 처리
Tree
↓
계층적인 데이터 구조
Heap
↓
우선순위가 높은 데이터를 빠르게 확인하고 처리
Heap은 트리의 개념을 기반으로 하지만, 일반적인 트리 탐색보다는 우선순위 관리에 특화된 자료구조라고 이해할 수 있다.
30. C++에서의 Heap
C++ STL에서는 Priority Queue뿐만 아니라 Heap을 직접 다룰 수 있는 함수도 제공한다.
대표적으로 다음과 같은 함수들이 있다.
std::make_heap
std::push_heap
std::pop_heap
std::sort_heap
따라서 C++에서 Heap을 공부할 때는 단순히 std::priority_queue의 사용법만 외우는 것이 아니라, 내부적으로 Heap이 어떤 원리로 동작하는지 이해하는 것이 중요하다.
전체적으로:
Heap의 원리 이해
↓
std::priority_queue 이해
↓
make_heap / push_heap / pop_heap 이해
↓
Heap Sort 이해
와 같은 흐름으로 연결할 수 있다.
31. 이번 학습에서 정리한 핵심
이번 10단계에서 가장 중요하게 이해한 부분은 Heap을 단순한 트리 자료구조로 보는 것이 아니라 우선순위 처리와 정렬 알고리즘으로 연결해서 이해하는 것이었다.
Heap은 완전 이진 트리의 구조를 사용하고, 부모와 자식 사이에 우선순위 관계를 유지한다.
Min Heap
→ 최솟값이 Root
Max Heap
→ 최댓값이 Root
새로운 값을 넣을 때는:
마지막 위치에 삽입
→ Sift Up
Root를 제거할 때는:
마지막 노드를 Root로 이동
→ Sift Down
한다.
그리고 이러한 Heap의 특성을 이용하면 Priority Queue를 효율적으로 구현할 수 있다.
Heap
↓
Priority Queue
↓
우선순위가 높은 데이터부터 처리
또한 Heap을 이용해 Heap Sort를 구현할 수 있다.
Heap
↓
Heap Sort
↓
O(N log N)
따라서 이번 단계의 핵심 흐름은 다음과 같이 정리할 수 있다.
Complete Binary Tree
↓
Heap
↙ ↘
Min Heap Max Heap
↓ ↓
최솟값 우선 최댓값 우선
↘ ↙
Priority Queue
↓
우선순위 처리
그리고 별도로:
Heap
↓
Heap Sort
↓
O(N log N)
으로 연결된다.
이번 단계에서는 Heap = 완전 이진 트리 + 부모/자식 간 우선순위 관계, Priority Queue = 우선순위에 따라 데이터를 처리하는 구조, Heap Sort = Heap의 특성을 이용한 정렬 알고리즘이라는 관계를 중심으로 이해하는 것이 핵심이었다.