부모가 자식보다 항상 크거나(최대 힙) 항상 작은(최소 힙) 규칙을 지키는 완전 이진 트리. "완전 이진 트리"는 위에서 아래로, 왼쪽에서 오른쪽으로 빈틈없이 채워진 트리를 말한다.
BST와 무엇이 다른가 — 가장 많이 헷갈린다
| BST | 힙 | |
|---|---|---|
| 보장하는 것 | 왼쪽 < 나 < 오른쪽 | 부모 > 자식 (또는 부모 < 자식) |
| 형제 사이 순서 | 있음 | 없음 |
| 최댓값 찾기 | 맨 오른쪽까지 내려감 | 루트, O(1) |
| 임의 값 탐색 | O(log n) | O(n) |
힙은 형제끼리의 크기를 보장하지 않는다. 그래서 "7이 어디 있나"를 물으면 전부 뒤져야 한다. 힙은 최댓값/최솟값만 빠르게 꺼내는 자료구조다.
배열 하나로 구현된다
완전 이진 트리라 빈칸이 없으므로 배열에 순서대로 담으면 된다.
9 배열: [9, 7, 6, 3, 5, 2]
/ \ 인덱스: 0 1 2 3 4 5
7 6
/ \ /
3 5 2
인덱스 i 기준
- 왼쪽 자식 = 2i + 1
- 오른쪽 자식 = 2i + 2
- 부모 = (i - 1) / 2
포인터가 필요 없어 메모리가 절약되고 캐시 지역성이 좋다.
삽입 — 끝에 넣고 위로 올린다 (sift-up)
- 배열 맨 뒤에 넣는다
- 부모와 비교해 규칙을 어기면 교환
- 규칙을 지킬 때까지 반복
최대 트리 높이만큼 올라가므로
O(log n)이다.
삭제 — 루트를 빼고 마지막을 올린 뒤 내린다 (sift-down)
- 루트(최댓값)를 꺼낸다
- 배열 마지막 원소를 루트 자리에 놓는다
- 자식 중 큰 쪽과 비교해 규칙을 어기면 교환하며 내려간다
역시
O(log n)이다.
힙 구성은 O(n) — 의외의 사실
n개를 하나씩 삽입하면 O(n log n)이지만, 배열을 통째로 놓고 아래에서부터
sift-down 하면 O(n)이다. 아래쪽 노드일수록 내려갈 거리가 짧아 전체 합이
n에 수렴하기 때문이다.
어디에 쓰이나
- 우선순위 큐 — 자바
PriorityQueue가 힙이다 - 힙 정렬 — 다 꺼내면 정렬된 순서
- 다익스트라 최단경로 — 가장 가까운 정점을 반복해서 꺼냄
- 상위 K개 뽑기 — 크기 K짜리 힙을 유지하면
O(n log K)