이번 편의 결과물: coding-test/12-tree-heap/에 트리 순회, 직접 만든 MinHeap, 힙 응용 문제, 그리고 힙으로 최적화한 다익스트라까지 4개 파일을 완성합니다. · 다루는 개념: 이진 트리 순회, 힙 속성, 배열 기반 MinHeap, 우선순위 큐로 다익스트라 최적화
이 편에서 만드는 파일
coding-test/12-tree-heap/
├── lib/
│ ├── MinHeap.js (+)
│ └── MinHeap.test.js (+)
├── 01-tree-traversal/
│ ├── solution.js (+)
│ └── solution.test.js (+)
├── 03-kth-smallest/
│ ├── solution.js (+)
│ └── solution.test.js (+)
└── 04-dijkstra-with-heap/
├── solution.js (+)
└── solution.test.js (+)MinHeap은 05편의 lib/Stack.js·Queue.js·Deque.js와 같은 방식으로 lib/ 폴더에 두는 재사용 가능한 자료구조입니다. 이 편의 문제 2가 바로 이 MinHeap을 만드는 실습이고, 문제 3·4는 완성된 MinHeap을 가져다 씁니다.
개념 정리
| 개념 | 설명 |
|---|---|
| 이진 트리 순회 | 전위(루트-왼쪽-오른쪽)·중위(왼쪽-루트-오른쪽)·후위(왼쪽-오른쪽-루트) 세 가지 방문 순서 |
| 힙(heap) 속성 | 부모가 항상 두 자식보다 작거나(최소 힙) 크다(최대 힙)는 규칙을 만족하는 완전 이진 트리 |
| 배열 기반 힙 | 힙을 배열로 표현하면 인덱스 i의 부모는 (i - 1) / 2, 왼쪽 자식은 i * 2 + 1, 오른쪽 자식은 i * 2 + 2로 계산할 수 있어 포인터 없이 구현할 수 있다 |
| 우선순위 큐 | ”가장 작은(또는 큰) 원소를 빠르게 꺼내는” 자료구조. 힙으로 구현하면 삽입·삭제가 O(log n)이다 |
11편의 다익스트라는 매 단계 “미방문 정점 중 최단거리”를 배열 전체에서 선형 탐색(O(V))했습니다. MinHeap을 쓰면 최솟값을 꺼내는 데 O(log n)만 걸려, 다익스트라 전체가 O(V²)에서 O((V + E)logV)로 줄어듭니다.
실습
1. 이진 트리 순회 — 재귀로 세 가지 순서 구현
문제: 이진 트리 노드 TreeNode(value, left, right)가 주어질 때, 전위·중위·후위 순회 결과를 배열로 반환하는 preorder, inorder, postorder를 구현합니다.
입출력 예
| 트리 | preorder | inorder | postorder |
|---|---|---|---|
| 루트 1, 왼쪽 2(자식 4, 5), 오른쪽 3 | [1,2,4,5,3] | [4,2,5,1,3] | [4,5,2,3,1] |
접근(복잡도): 세 함수 모두 “노드가 없으면 빈 배열”이 종료 조건입니다. 나머지는 자신의 값과 왼쪽·오른쪽 서브트리 재귀 결과를 순서만 다르게 이어 붙입니다. 노드 수 n에 대해 O(n)입니다.
코드
// coding-test/12-tree-heap/01-tree-traversal/solution.js
// 시간복잡도: O(n) — 노드 n개를 각각 한 번씩 방문한다
// 공간복잡도: O(n) — 순회 결과 배열과 재귀 호출 스택을 사용한다
export class TreeNode {
constructor(value, left = null, right = null) {
this.value = value;
this.left = left;
this.right = right;
}
}
export function preorder(root) {
if (root === null) {
return [];
}
return [root.value, ...preorder(root.left), ...preorder(root.right)];
}
export function inorder(root) {
if (root === null) {
return [];
}
return [...inorder(root.left), root.value, ...inorder(root.right)];
}
export function postorder(root) {
if (root === null) {
return [];
}
return [...postorder(root.left), ...postorder(root.right), root.value];
}테스트
// coding-test/12-tree-heap/01-tree-traversal/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { TreeNode, preorder, inorder, postorder } from './solution.js';
const tree = new TreeNode(1, new TreeNode(2, new TreeNode(4), new TreeNode(5)), new TreeNode(3));
test('전위 순회는 루트-왼쪽-오른쪽 순서다', () => {
assert.deepStrictEqual(preorder(tree), [1, 2, 4, 5, 3]);
});
test('중위 순회는 왼쪽-루트-오른쪽 순서다', () => {
assert.deepStrictEqual(inorder(tree), [4, 2, 5, 1, 3]);
});
test('후위 순회는 왼쪽-오른쪽-루트 순서다', () => {
assert.deepStrictEqual(postorder(tree), [4, 5, 2, 3, 1]);
});
test('빈 트리는 빈 배열을 반환한다', () => {
assert.deepStrictEqual(preorder(null), []);
});node --test 01-tree-traversal/solution.test.js
# tests 4, pass 4, fail 0함정: [...preorder(root.left), ...preorder(root.right)]처럼 스프레드로 배열을 매번 새로 만드는 방식은 코드가 짧지만 노드마다 배열 복사가 일어나 실제로는 O(n²)에 가깝습니다. 입력 크기가 매우 크면 하나의 결과 배열에 push하는 방식으로 바꿔야 합니다.
2. MinHeap 직접 구현 — 배열과 비교 함수
문제: push(value)로 원소를 넣고 pop()으로 가장 작은 원소를 꺼내는 MinHeap 클래스를 배열 기반으로 구현합니다. 숫자뿐 아니라 [거리, 정점] 같은 튜플도 비교 함수를 넘겨 다룰 수 있어야 합니다.
입출력 예
| 연산 순서 | 결과 |
|---|---|
push(5) push(2) push(8) pop() pop() pop() | 2, 5, 8 순서로 꺼내짐 |
접근(복잡도): push는 배열 끝에 넣고 부모와 비교해 더 작으면 자리를 바꾸는 것을 반복(bubble up)합니다. pop은 맨 앞(최솟값)을 꺼내고 마지막 원소를 맨 앞으로 옮긴 뒤 더 작은 자식과 계속 자리를 바꿉니다(bubble down). 둘 다 트리 높이만큼, O(log n)입니다. [distance, vertex] 같은 배열은 <로 직접 비교하면 문자열로 바뀌어 잘못 비교되므로, 생성자에서 받은 비교 함수로만 비교합니다.
코드
// coding-test/12-tree-heap/lib/MinHeap.js
export class MinHeap {
#items = [];
#compare;
constructor(compare = (a, b) => a - b) {
this.#compare = compare;
}
get size() {
return this.#items.length;
}
peek() {
return this.#items[0];
}
push(value) {
this.#items.push(value);
this.#bubbleUp(this.#items.length - 1);
}
pop() {
const top = this.#items[0];
const last = this.#items.pop();
if (this.#items.length > 0) {
this.#items[0] = last;
this.#bubbleDown(0);
}
return top;
}
#bubbleUp(index) {
let current = index;
while (current > 0) {
const parent = Math.floor((current - 1) / 2);
if (this.#compare(this.#items[parent], this.#items[current]) <= 0) {
break;
}
[this.#items[parent], this.#items[current]] = [this.#items[current], this.#items[parent]];
current = parent;
}
}
#bubbleDown(index) {
let current = index;
const length = this.#items.length;
while (true) {
const left = current * 2 + 1;
const right = current * 2 + 2;
let smallest = current;
if (left < length && this.#compare(this.#items[left], this.#items[smallest]) < 0) {
smallest = left;
}
if (right < length && this.#compare(this.#items[right], this.#items[smallest]) < 0) {
smallest = right;
}
if (smallest === current) {
break;
}
[this.#items[current], this.#items[smallest]] = [this.#items[smallest], this.#items[current]];
current = smallest;
}
}
}테스트
// coding-test/12-tree-heap/lib/MinHeap.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { MinHeap } from './MinHeap.js';
test('넣은 순서와 상관없이 가장 작은 값부터 꺼낸다', () => {
const heap = new MinHeap();
for (const value of [5, 2, 8, 1, 9, 3]) {
heap.push(value);
}
const popped = [];
while (heap.size > 0) {
popped.push(heap.pop());
}
assert.deepStrictEqual(popped, [1, 2, 3, 5, 8, 9]);
});
test('peek은 꺼내지 않고 최솟값만 확인한다', () => {
const heap = new MinHeap();
heap.push(4);
heap.push(1);
assert.strictEqual(heap.peek(), 1);
assert.strictEqual(heap.size, 2);
});
test('비교 함수를 넘기면 튜플도 기준값으로 정렬한다', () => {
const heap = new MinHeap((a, b) => a[0] - b[0]);
heap.push([10, 'a']);
heap.push([2, 'b']);
heap.push([100, 'c']);
assert.deepStrictEqual(heap.pop(), [2, 'b']);
assert.deepStrictEqual(heap.pop(), [10, 'a']);
});node --test lib/MinHeap.test.js
# tests 3, pass 3, fail 0함정: [distance, vertex] 튜플을 기본 비교 함수(a - b)로 그대로 넣으면 배열끼리 뺄셈이 되어 NaN이 나옵니다. 튜플을 다룰 때는 반드시 (a, b) => a[0] - b[0]처럼 비교 기준을 명시한 비교 함수를 생성자에 넘겨야 합니다.
3. K번째로 작은 값 — 힙 활용
문제: 정수 배열 numbers와 k가 주어질 때, k번째로 작은 값을 반환하는 solution(numbers, k)를 MinHeap으로 구현합니다.
입출력 예
| 입력 | 출력 |
|---|---|
numbers=[7,4,6,1,9], k=2 | 4 |
numbers=[7,4,6,1,9], k=1 | 1(최솟값) |
접근(복잡도): 모든 원소를 힙에 넣고(O(n log n)) k번 pop해 마지막 값을 반환합니다. 정렬과 시간복잡도는 같지만, k가 n보다 훨씬 작으면 힙 크기를 k로 제한해 더 빠르게 만들 수 있습니다(직접 해보기 참고).
코드
// coding-test/12-tree-heap/03-kth-smallest/solution.js
// 시간복잡도: O(n log n) — 원소 n개를 힙에 넣고(O(n log n)) k번 꺼낸다
// 공간복잡도: O(n) — 모든 원소를 힙에 저장한다
import { MinHeap } from '../lib/MinHeap.js';
export function solution(numbers, k) {
const heap = new MinHeap();
for (const number of numbers) {
heap.push(number);
}
let result;
for (let i = 0; i < k; i += 1) {
result = heap.pop();
}
return result;
}테스트
// coding-test/12-tree-heap/03-kth-smallest/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
test('k번째로 작은 값을 찾는다', () => {
assert.strictEqual(solution([7, 4, 6, 1, 9], 2), 4);
});
test('k가 1이면 최솟값이다', () => {
assert.strictEqual(solution([7, 4, 6, 1, 9], 1), 1);
});
test('k가 배열 길이와 같으면 최댓값이다', () => {
assert.strictEqual(solution([7, 4, 6, 1, 9], 5), 9);
});node --test 03-kth-smallest/solution.test.js
# tests 3, pass 3, fail 0함정: “K번째로 큰 값”과 헷갈리기 쉽습니다. 이 문제는 최소 힙으로 작은 값부터 꺼내므로 k번째로 꺼낸 값이 k번째로 작은 값입니다. 반대로 K번째로 큰 값을 구하려면 MaxHeap을 쓰거나 비교 함수 부호를 반대로 넘깁니다.
4. 다익스트라 최적화 — 힙으로 O((V+E)logV)
문제: 11편의 solution(graph, start)(다익스트라)와 같은 입력을 받아 같은 결과를 반환하되, 직접 만든 MinHeap으로 다음에 볼 정점을 고르는 solution(graph, start)를 구현합니다.
입출력 예
| 입력(11편과 같은 그래프) | 출력 |
|---|---|
solution(graph, 0) | [0, 2, 1, 3](11편의 solution(graph, 0)과 동일) |
접근(복잡도): 11편은 미방문 정점 중 최단거리를 배열 선형 탐색(O(V))으로 찾았습니다. 이 버전은 [거리, 정점]을 담는 MinHeap에서 pop으로 즉시 최단거리 정점을 꺼냅니다(O(log V)). 힙에는 더 짧은 경로를 찾을 때마다 새 항목을 그냥 추가하고, 꺼낸 거리가 이미 확정된 거리보다 크면(오래된 값이면) 건너뜁니다. 간선마다 최대 한 번씩 힙에 들어가 전체는 O((V + E)logV)입니다.
코드
// coding-test/12-tree-heap/04-dijkstra-with-heap/solution.js
// 시간복잡도: O((V + E)logV) — 간선마다 최대 한 번씩 힙에 넣고 꺼낸다
// 공간복잡도: O(V + E) — 거리 배열과 힙, 인접 리스트를 사용한다
import { MinHeap } from '../lib/MinHeap.js';
export function solution(graph, start) {
const vertexCount = graph.length;
const distance = new Array(vertexCount).fill(Infinity);
distance[start] = 0;
const heap = new MinHeap((a, b) => a[0] - b[0]);
heap.push([0, start]);
while (heap.size > 0) {
const [currentDistance, current] = heap.pop();
if (currentDistance > distance[current]) {
continue;
}
for (const [next, weight] of graph[current]) {
const candidate = currentDistance + weight;
if (candidate < distance[next]) {
distance[next] = candidate;
heap.push([candidate, next]);
}
}
}
return distance;
}테스트
// coding-test/12-tree-heap/04-dijkstra-with-heap/solution.test.js
import { test } from 'node:test';
import assert from 'node:assert/strict';
import { solution } from './solution.js';
const graph = [
[[1, 4], [2, 1]],
[[3, 1]],
[[1, 1], [3, 5]],
[],
];
test('11편의 O(V^2) 다익스트라와 같은 결과가 나온다', () => {
assert.deepStrictEqual(solution(graph, 0), [0, 2, 1, 3]);
});
test('가중치가 두 자리 수 이상이어도 정확하다', () => {
const bigGraph = [[[1, 15], [2, 100]], [[2, 1]], []];
assert.deepStrictEqual(solution(bigGraph, 0), [0, 15, 16]);
});
test('도달할 수 없는 정점은 Infinity다', () => {
const isolated = [[], [], []];
assert.strictEqual(solution(isolated, 0)[1], Infinity);
});node --test 04-dijkstra-with-heap/solution.test.js
# tests 3, pass 3, fail 0함정: 힙에는 정점당 한 번이 아니라 “더 짧은 경로를 찾을 때마다” 새 항목이 들어가 같은 정점이 여러 번 쌓일 수 있습니다. 그래서 pop 직후 currentDistance > distance[current]로 이미 낡은 값인지 반드시 확인해야 합니다. 이 확인이 없으면 오래된 거리로 이웃을 잘못 갱신할 수 있습니다.
직접 해보기
- 문제 3의
solution(kthSmallest)을 힙 크기를 항상k이하로 유지하는 방식(최대 힙을 쓰고 크기가k를 넘으면 가장 큰 값을 버림)으로 바꿔,numbers가 아주 클 때 더 적은 메모리로 동작하게 만들어보세요. - 문제 4의
solution(dijkstraWithHeap)의distance배열만으로는 실제 경로를 알 수 없습니다. 11편의 “직접 해보기”에서 다룬predecessor배열을 이 힙 버전에도 추가해보세요.
정답 보기(1번)
부호를 반대로 넘긴 new MinHeap((a, b) => b - a)(최대 힙처럼 동작)를 쓰고, numbers를 순회하며 힙 크기가 k 미만이면 그냥 넣고, k에 도달했는데 새 값이 힙의 최댓값(맨 위)보다 작으면 맨 위를 pop한 뒤 새 값을 push합니다. 순회가 끝나면 힙에는 가장 작은 k개만 남고, 그중 최댓값(맨 위)이 k번째로 작은 값입니다.
자주 하는 실수
| 증상 | 원인 | 고치는 법 |
|---|---|---|
| 튜플을 힙에 넣었더니 순서가 뒤죽박죽 | 비교 함수 없이 기본값(a - b)을 그대로 씀 | [거리, 정점]처럼 튜플을 다룰 때는 반드시 비교 함수를 생성자에 넘긴다 |
| 힙 기반 다익스트라가 11편 결과와 다름 | pop 직후 낡은 거리인지 확인하지 않음 | currentDistance > distance[current]이면 그 항목을 건너뛴다 |
bubbleDown에서 배열 범위를 벗어남 | 자식 인덱스 계산 후 length 검사를 빼먹음 | left < length, right < length를 먼저 확인한 뒤에만 비교한다 |