스택과 큐 글 마지막에 예고했던 자료구조 시리즈 2편입니다. 이번 주인공은 힙(Heap)인데, 시작 전에 오해 하나부터 정리해야 합니다.
관련 글 스택(Stack)과 큐(Queue) 완벽 정리, Swift에 Stack 타입이 없는 이유 (removeFirst 함정까지)에서 배경 개념과 이어지는 적용 사례를 함께 확인할 수 있습니다.
자료구조 힙은 메모리 힙과 이름만 같고 아무 관련이 없습니다. 메모리의 힙 영역은 동적 할당 공간이고 오늘 다룰 힙은 “최솟값(또는 최댓값)을 O(1)에 꺼내기 위한 트리”입니다.
스택 vs 힙 글의 그 힙을 기대했다면, 여기는 완전히 다른 세계입니다.
힙이 풀려는 문제는 명확합니다.
“가장 급한 것부터 처리하고 싶다. 그런데 전체를 정렬해 두는 건 아깝다.”
정렬은 과잉이다
우선순위가 가장 높은 작업부터 꺼내는 대기열을 만든다고 해봅시다. 배열을 매번 정렬하면 삽입마다 O(n log n)입니다.
정렬된 상태를 유지하며 삽입 위치를 찾아도 원소 이동 때문에 O(n)입니다.
그런데 곰곰이 생각하면, 우리에게 필요한 건 전체가 정렬된 상태가 아닙니다. 지금 가장 급한 것 하나만 즉시 알면 됩니다.
2등이 누군지는 1등이 빠진 다음에 알아도 늦지 않습니다.
힙은 정확히 이만큼만 약속하는 자료구조입니다. 그래서 삽입도 삭제도 O(log n)에 끝납니다.
“덜 약속할수록 빨라진다”는 자료구조 설계의 대표적인 트레이드오프입니다.
힙의 규칙: 부모는 자식보다 작다, 그게 전부
최소 힙(min-heap)은 완전 이진 트리이면서 규칙이 딱 하나 있습니다.
모든 부모는 자기 자식들보다 작거나 같다.
형제끼리 누가 큰지는 관심 없습니다. 왼쪽 서브트리가 오른쪽보다 작을 필요도 없고요.
오직 부모-자식 관계만 지키면 됩니다. 이 느슨함 덕분에 루트에는 항상 전체 최솟값이 있고 그 이상은 보장하지 않습니다.
삽입(sift up): 트리의 맨 끝에 붙인 뒤, 부모보다 작으면 부모와 교환하며 위로 올라갑니다. 트리 높이만큼만 움직이니 O(log n)입니다.
최솟값 꺼내기(sift down): 루트를 빼고 맨 끝 원소를 루트로 올린 뒤, 두 자식 중 작은 쪽과 교환하며 내려갑니다. 역시 O(log n)입니다.
배열로 트리를 만드는 마법
힙의 구현이 우아한 지점이 여기입니다. 완전 이진 트리는 빈칸 없이 왼쪽부터 차곡차곡 채워지므로, 포인터 없이 배열에 순서대로 눕힐 수 있습니다.
인덱스: 0 1 2 3 4 5
값: [1, 3, 2, 7, 4, 5]인덱스 계산만으로 가족 관계가 나옵니다.
- 부모:
(i - 1) / 2 - 왼쪽 자식:
2i + 1, 오른쪽 자식:2i + 2
노드 객체도, 자식 포인터도, 힙 메모리 할당도 없습니다. 배열 vs 연결 리스트에서 다룰 캐시 지역성의 이점을 그대로 누리면서 트리의 논리 구조만 빌려 쓰는 셈입니다.
Swift로 뼈대를 그리면 이렇습니다.
struct MinHeap<Element: Comparable> {
private var elements: [Element] = []
var min: Element? { elements.first } // O(1)
mutating func insert(_ value: Element) { // O(log n)
elements.append(value)
siftUp(from: elements.count - 1)
}
mutating func removeMin() -> Element? { // O(log n)
guard !elements.isEmpty else { return nil }
elements.swapAt(0, elements.count - 1)
let min = elements.removeLast()
siftDown(from: 0)
return min
}
}siftUp/siftDown은 위에서 설명한 교환 반복입니다.
참고로 기존 배열 전체를 힙으로 만드는 build-heap은 원소마다 삽입하는 O(n log n)이 아닙니다. 아래쪽 절반에서부터 sift down하면 **O(n)**에 끝납니다 — 면접에서 종종 나오는 디테일입니다.
실무에서 힙이 서 있는 자리
우선순위 큐가 곧 힙입니다. 스택·큐 글의 표현을 빌리면, 큐는 먼저 온 순서, 우선순위 큐는 급한 순서로 꺼내는 대기열이고 그 표준 구현체가 힙입니다.
- OS 스케줄러: 우선순위 높은 프로세스부터 CPU를 배정
- 다익스트라 최단 경로: “지금까지 발견한 경로 중 가장 짧은 것”을 반복해서 꺼내는 알고리즘 — 힙이 없으면 성능이 무너집니다
- 타이머 관리: 수많은 타이머 중 가장 먼저 울릴 것만 알면 되는 시스템 내부 구조
- 힙 정렬: 전부 넣고 전부 빼면 O(n log n) 정렬이 됩니다. 추가 메모리 없이 제자리 정렬이 되는 게 강점
- Top-K 문제: “스트림에서 가장 큰 K개 유지” — 크기 K짜리 최소 힙으로 O(n log K)에 풉니다. 코딩 테스트 단골 패턴입니다
Swift 표준 라이브러리에는 힙이 없습니다. 스택·큐 글의 Deque처럼, 애플의 swift-collections 패키지가 Heap을 제공합니다.
min과 max 양쪽을 O(log n)에 지원하는 min-max heap 구현입니다. 코딩 테스트처럼 외부 패키지가 안 되는 환경이라면 위의 MinHeap 뼈대를 손에 익혀두는 게 실전적입니다.
정리
- 자료구조 힙은 메모리 힙과 이름만 같습니다 — “최솟값을 즉시 꺼내는 트리”입니다
- 규칙은 부모 ≤ 자식 하나뿐 — 전체 정렬을 포기한 대가로 삽입·삭제가 O(log n)입니다
- 완전 이진 트리라서 배열에 포인터 없이 눕힐 수 있습니다 — 부모
(i-1)/2, 자식2i+1,2i+2 - 우선순위 큐의 표준 구현이 힙이고, 다익스트라·스케줄러·Top-K가 대표 활용처입니다
- Swift에서는 swift-collections의
Heap, 코딩 테스트에서는 직접 구현이 정석입니다
다음 편은 해시 테이블입니다. Swift Dictionary가 어떻게 O(1)을 만들어내는지, 그리고 Hashable이 요구하는 것들의 진짜 의미를 다룹니다.
API와 버전 근거는 swift-collections Heap에서 2026-08-17에 확인했습니다.
API와 버전 근거는 NIST Dictionary of Algorithms: Priority Queue에서 2026-08-17에 확인했습니다.
API와 버전 근거는 NIST Dictionary of Algorithms: Heap에서 2026-08-17에 확인했습니다.
출처 및 확인 기준
- swift-collections Heap — Apple · 공식 문서 · 확인 2026-08-17 · 근거: Swift Heap API와 최소·최대 힙 동작
- NIST Dictionary of Algorithms: Priority Queue — NIST · 공식 데이터 · 확인 2026-08-17 · 근거: 우선순위 큐의 추상 자료형 정의
- NIST Dictionary of Algorithms: Heap — NIST · 공식 데이터 · 확인 2026-08-17 · 근거: 배열 기반 힙의 구조와 연산 특성