jebae's dev blog

우선 순위 큐와 힙

javascript 를 이용한 우선 순위 큐 구현과 시간 복잡도 계산

2021년 05월 20일

우선 순위 큐

우선 순위 큐는 최댓값, 최솟값을 찾는데 효율적인 자료 구조입니다. C++, python 을 포함한 많은 언어들이 내장 라이브러리를 통해 우선 순위 큐를 지원하는 것과 달리 javascript 는 지원하지 않고 있습니다. 그래서 종종 외부 라이브러리를 설치할 수 없는 프로젝트나 알고리즘 테스트에서 우선 순위 큐가 필요할 때, 우선 순위 큐를 직접 구현해야 하는 귀찮음이 따릅니다. 이 포스트에서는 javascript 를 사용해 우선 순위 큐를 구현해 보고 더 나아가 상황에 따라 다른 구현 코드로 시간 복잡도를 낮출 수 있는 방법을 알아보겠습니다.





힙 (heap)

우선 순위 큐는 힙 자료구조로 만들어집니다. 힙은 그림과 같이 이진트리를 기본으로 한 자료구조입니다.

힙은 위에서 아래로 한 계층의 노드가 모두 채워질 때까지, 왼쪽에서 오른쪽으로 노드를 삽입합니다. 위 그림의 노드 왼편에 써 있는 번호는 삽입된 순서를 의미합니다. 제거 시 최하위 레벨의 오른쪽 노드부터 제거합니다. 이런 성질은 힙이 아래와 같이 어느 한쪽 서브 트리의 깊이가 다른 쪽보다 2 이상 큰 형태가 될 수 없도록 만듭니다.

보통 트리는 노드 객체를 선언하고 노드의 속성 .left, .right 를 이용해 구현하지만 힙은 위와 같은 성질 덕분에 배열로 구현할 수 있습니다. 아래 힙 트리의 노드를 위에서 아래, 왼쪽에서 오른쪽 방향으로 따라가보면 [ 42, 20, 4, 12, 7, 8, 19, 1, 67, 38, 24, 15 ] 와 같이 정리됩니다.

배열로 정리된 힙에서 자식 노드는 자신의 인덱스에서 1을 뺀 뒤 2로 나누었을 때 부모 노드의 인덱스를 얻습니다. 거꾸로 부모 노드의 인덱스에 2를 곱한 뒤 1을 더하면 왼쪽 자식 노드의 인덱스를, 2를 곱한 뒤 2를 더하면 오른쪽 자식의 인덱스를 얻습니다.

이같은 힙의 편리한 성질은 우선 순위 큐를 구현하는데 중요한 역할을 합니다.





힙을 이용한 우선 순위 큐

크기가 n 인 정수 배열이 정렬되지 않은 상태라고 할 때 최솟값을 찾으려면 O(n) 의 시간 복잡도를 필요로 합니다. 만약 k 개의 최솟값을 찾아야 한다면 첫번째 작은 값, 두번째 작은 값, ... k 번째 작은 값을 찾기 위해 O(kn) 으로 배열을 탐색하거나 배열을 정렬해 O(n logn) 으로 탐색할 수도 있습니다.

최솟값 또는 최댓값을 찾는 또 다른 한가지 효율적인 방법은 힙을 이용한 우선 순위 큐를 활용하는 것입니다. 최솟값을 찾는 우선 순위 큐를 구현한다고 할 때 큐의 첫번째 엔트리는 다른 엔트리들보다 작은 값이어야 합니다. 여기서 큐의 첫번째 엔트리는 힙의 루트 노드에 해당합니다. 조금 더 일반적으로 정의하면, 힙의 부모 노드는 항상 자식 노드보다 작거나 같은 값이어야 합니다. 이 때 루트 노드는 모든 노드의 부모이므로 당연히 가장 작은 값을 가집니다. 아래 그림은 부모 노드의 값이 항상 자식보다 작은 힙 트리를 보여주고 있습니다.

그림의 힙을 배열로 구현했다고 할 때 최솟값은 배열의 0번째 엔트리입니다.

우선 순위 큐 역시 여느 큐와 마찬가지로 엔트리를 삽입하는 메소드 push, 제거하는 메소드 pop 를 가집니다. 메소드 push 와 pop 은 그 실행 결과로 항상 부모 노드의 값이 자식 노드보다 작거나 같도록 유지해야 합니다.

먼저 push 를 구현해 보겠습니다.

// const heap = [ ... ];

function heappush(heap, elem) {
	...
}

함수 heappush 는 배열로 구현된 힙 heap 에 elem 를 삽입하고 힙의 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같도록 유지해야 합니다. 힙은 위에서 아래로, 왼쪽부터 오른쪽으로 노드를 삽입하므로 heap.push(elem) 을 실행하면 자연스럽게 최하위 레벨의 가장 오른쪽에 노드가 추가됩니다.

추가된 노드의 값 2는 부모 노드인 15보다 작으므로 최소힙의 조건을 만족하지 않습니다. 최소힙을 유지하기 위해 heappush 는 추가된 노드에 대해 조건을 만족할 때까지 부모 노드와 스왑을 반복합니다. 위 그림의 경우 추가된 노드 2를 부모 노드 15와 스왑해 서브 트리에 대해 조건을 만족시킵니다.

이 때 힙의 부모 인덱스는 자식 인덱스에서 1을 뺀 뒤 2로 나눈 값입니다. 예시의 경우 추가된 노드의 인덱스는 12이므로 부모 노드의 인덱스는 (12 - 1) / 2 = 5 입니다. 새로운 노드의 추가부터 부모 노드와 값을 비교 후 스왑하는 과정까지 코드로 작성해 보겠습니다.

// const heap = [ ... ];

function heappush(heap, elem) {
	heap.push(elem);

	// 추가된 노드의 인덱스
	let idx = heap.length - 1;

	// 부모 노드의 인덱스
	const parent = Math.trunc((idx - 1) / 2);

	// 자식 노드의 값이 부모 노드보다 작다면 스왑
	if (heap[idx] < heap[parent]) {
		const temp = heap[parent];

		heap[parent] = heap[idx];
		heap[idx] = temp;
	}
}

한편 노드 2는 스왑된 위치에서의 새로운 부모 노드 4보다 값이 작으므로 한 번 더 스왑합니다.

두번째 스왑된 위치에서 새로운 부모 노드의 값 1은 2보다 작으므로 더 이상 스왑을 진행하지 않습니다. 이 과정을 코드에 적용해 보겠습니다.

// const heap = [ ... ];

function heappush(heap, elem) {
	heap.push(elem);

	// 추가된 노드의 인덱스
	let idx = heap.length - 1;

	// 노드가 루트에 위치하면 더 이상 부모 노드가 없으므로 반복을 중단
	while (idx > 0) {
		// 부모 노드의 인덱스
		const parent = Math.trunc((idx - 1) / 2);

		// 자식 노드의 값이 부모 노드보다 작다면 스왑
		if (heap[idx] < heap[parent]) {
			const temp = heap[parent];

			heap[parent] = heap[idx];
			heap[idx] = temp;
			idx = parent;
		} else {
			break ;
		}
	}
}

heappush 함수는 추가된 노드가 루트 노드가 될 때까지 스왑을 반복한다고 할 때 힙 트리의 계층 개수만큼 비교, 스왑 연산을 시행합니다. 힙 트리의 전체 노드 개수를 n 이라 할 때 힙 트리 계층의 개수는 log2nlog_2n 입니다. 예를 들어 트리의 노드 개수가 8개라면 log28=3log_28 = 3 이므로 3번 비교, 스왑 연산을 시행합니다. 따라서 heappush 함수의 시간 복잡도는 O(log n) 이라 할 수 있습니다.



노드 추가 함수에 이어 노드 제거 함수 heappop 을 구현해볼 차례입니다. 힙 트리에서 노드 삭제는 최하위 레벨의 가장 오른쪽부터 실행됩니다.

위 힙 트리에서 최하위 가장 오른쪽 노드의 값은 20입니다. 일반적인 힙 트리라면 20을 제거한 뒤 반환하겠지만 우선 순위 큐의 힙에서 단순히 제거만 실행한다면 최솟값을 찾는 자료 구조로서 전혀 역할하지 못합니다.

우선 순위 큐의 heappop 은 먼저 트리의 가장 작은 값인 루트 노드를 제거한 뒤 그 자리를 힙 트리의 가장 끝 값으로 메꿉니다.

위 동작은 가장 작은 값을 반환값으로 사용할 수 있는 동시에 최하위 레벨의 가장 오른쪽 노드 제거를 가능케 합니다. 이 부분은 아주 간단하게 코드로 작성할 수 있습니다.

function heappop(heap) {
	// 루트 노드 제거
	const res = heap.shift();

	// 루트 노드 자리를 최하위 가장 오른쪽 노드로 메꿈
	heap.unshift(heap.pop());

	...

	return res;
}

남은 프로세스는 새롭게 바뀐 루트 노드부터 트리의 부모 노드 값이 자식보다 작도록 유지하는 것입니다. 루트 노드가 교체된 아래 그림에서 루트 노드의 두 자식 노드 7과 4는 각각의 자식 노드들보다 항상 작은 값입니다.

따라서 두 자식 노드 중 더 작은 값과 루트 노드를 스왑하면 힙 트리는 가장 작은 값을 루트 노드로서 가지게 됩니다.

이 부분을 부모와 자식 노드의 인덱스 상관 관계를 이용해 코드로 구현해 보겠습니다.

function heappop(heap) {
	// 루트 노드 제거
	const res = heap.shift();

	// 루트 노드 자리를 최하위 가장 오른쪽 노드로 메꿈
	heap.unshift(heap.pop());

	// 루트 노드와 그 자식 노드들의 인덱스
	const idx = 0;
	const left = idx * 2 + 1;
	const right = idx * 2 + 2;

	let next = idx;

	// 루트 노드와 왼쪽 자식 노드를 비교
	if (heap[left] < heap[next])
		next = left;

	// 루트 노드와 왼쪽 자식 노드 중 작은 쪽과 오른쪽 자식 노드를 비교
	if (heap[right] < heap[next])
		next = right;

	// 세 노드 루트와 왼쪽, 오른쪽 자식 중 가장 작은 노드가 루트가 아닐 경우 스왑
	if (idx !== next) {
		const temp = heap[idx];

		heap[idx] = heap[next];
		heap[next] = temp;
	}

	...

	return res;
}

스왑이 완료된 뒤 노드 20은 새로운 자식 노드 15, 19 중 더 작은 값 15와 한 번 더 스왑합니다.

두번째 스왑이 완료된 뒤 노드 20은 자식 노드를 가지고 있지 않으므로 더 이상 진행하지 않습니다. 반복을 적용해 코드를 수정해 보겠습니다.

function heappop(heap) {
	// 루트 노드 제거
	const res = heap.shift();

	// 루트 노드를 제거한 상태에서 힙 트리에 노드가 없다면 더 이상 프로세스를 진행하지 않음
	if (heap.length === 0)
		return res;

	// 루트 노드 자리를 최하위 가장 오른쪽 노드로 메꿈
	heap.unshift(heap.pop());

	let idx = 0;

	// 더 이상 자식 노드가 없을 때 까지 반복
	while (idx * 2 + 1 < heap.length) {
		// 부모 노드와 그 자식 노드들의 인덱스
		let next = idx;
		const left = idx * 2 + 1;
		const right = idx * 2 + 2;

		// 부모 노드와 왼쪽 자식 노드를 비교
		if (heap[left] < heap[next])
			next = left;

		// 부모 노드와 왼쪽 자식 노드 중 작은 쪽과 오른쪽 자식 노드를 비교
		// 이 때 오른쪽 자식 노드가 있는지 확인
		if (right < heap.length && heap[right] < heap[next])
			next = right;

		// 부모 노드가 가장 작은 경우 반복을 중지
		if (idx === next)
			break ;

		// 부모 노드와 가장 작은 자식 노드를 스왑
		const temp = heap[idx];

		heap[idx] = heap[next];
		heap[next] = temp;
		idx = next;
	}

	return res;
}

heappop 은 heappush 와 마찬가지로 최대한 힙 트리의 계층 개수만큼 스왑하므로 시간 복잡도는 O(log n) 입니다. 이제 heappush 와 heappop 함수를 이용해 정렬 없이 최솟값을 찾을 수 있습니다. 최댓값을 찾는 우선 순위 큐는 비교 연산의 부호만 바꾸어 구현할 수 있습니다. 주석을 제거해보면 함수의 길이도 길지 않은 편이라 우선순위 큐가 필요할 때 부담없이 구현해서 사용해 보시기 바랍니다.

function heappush(heap, elem) {
	heap.push(elem);

	let idx = heap.length - 1;

	while (idx > 0) {
		const parent = Math.trunc((idx - 1) / 2);

		if (heap[idx] < heap[parent]) {
			const temp = heap[parent];

			heap[parent] = heap[idx];
			heap[idx] = temp;
			idx = parent;
		} else {
			break ;
		}
	}
}

function heappop(heap) {
	const res = heap.shift();

	if (heap.length === 0)
		return res;

	heap.unshift(heap.pop());

	let idx = 0;

	while (idx * 2 + 1 < heap.length) {
		let next = idx;
		const left = idx * 2 + 1;
		const right = idx * 2 + 2;

		if (heap[left] < heap[next])
			next = left;

		if (right < heap.length && heap[right] < heap[next])
			next = right;

		if (idx === next)
			break ;

		const temp = heap[idx];

		heap[idx] = heap[next];
		heap[next] = temp;
		idx = next;
	}

	return res;
}





기존의 배열을 우선 순위 큐로 바꾸는 방법

최솟값을 찾는 어떤 문제는 비교할 데이터가 없는 상태에서 시작해 하나씩 큐에 추가하면서 이전에 추가된 데이터와 비교할 것을 요구합니다. 예를 들어 다익스트라 알고리즘은 다음 노드로의 엣지들을 큐에 추가하고 최소 누적 비용의 경로를 큐에서 삭제합니다. 이 경우 heappush, heappop 함수를 이용한 우선 순위 큐를 사용하면 다익스트라 알고리즘을 구현할 수 있습니다.

출처: 위키피디아



반면 이미 주어져 있는 데이터를 우선 순위 큐 형태로 변환해야 하는 경우도 있습니다. 예를 들어 아래 arr 배열을 우선 순위 큐 형태로 바꾼다고 하면, heappush 함수를 이용해 새로운 배열 pq 에 arr 의 값들을 하나씩 삽입하면 됩니다.

const arr = [4, 6, 2, 3, 1, 5];
const pq = [];

for (const num of arr) {
	heappush(pq, num);
}

이 경우 arr 의 크기 n 만큼의 반복횟수와 heappush 의 시간 복잡도 O(log n) 를 곱해 O(n log n) 으로 우선 순위 큐를 만들어 냅니다. 하지만 이 방법보다 더 빠르고 메모리도 아끼는 방법이 있습니다.



function heapify(heap, idx) {
	while (idx * 2 + 1 < heap.length) {
		let next = idx;
		const left = idx * 2 + 1;
		const right = idx * 2 + 2;

		if (heap[left] < heap[next])
			next = left;

		if (right < heap.length && heap[right] < heap[next])
			next = right;

		if (idx === next)
			break ;

		const temp = heap[idx];

		heap[idx] = heap[next];
		heap[next] = temp;
		idx = next;
	}
}

함수 heapify 는 heap 의 idx 번째 노드를 루트로 갖는 서브 트리가 우선 순위 큐의 조건을 만족시키도록 합니다. 서브 트리의 부모 노드가 두 자식 노드들보다 작을 때 까지 스왑을 반복하는 것입니다. heappop 의 주요 로직과 아주 똑같습니다.

우선 순위 큐의 루트 노드는 노드들 중 가장 작은 값을 가지고 있습니다. 루트 노드의 왼쪽과 오른쪽 두 자식 노드는 각각의 서브 트리에서 가장 작은 값을 가지고 있습니다. 마찬가지로 그 자식의 자식 노드 역시 각각의 서브 트리에서 가장 작은 값을 가지고 있습니다.

즉 힙 트리의 가장 작은 서브 트리부터 가장 큰 트리까지 부모 노드가 자식 노드보다 작도록 조건을 만족시켜 나가면 힙 트리는 우선 순위 큐가 됩니다. 가장 작은 서브 트리의 부모 노드는 리프 노드들의 부모 노드입니다. 아래 그림은 리프 노드들의 부모 노드인 3, 4, 5번째 노드들에 heapify 를 적용하는 과정을 보여주고 있습니다.

이후 루트 노드에 도달할 때 까지 부모 노드들에 대해 heapify 를 반복하면 가장 작은 서브 트리부터 전체 트리까지 우선 순위 큐의 조건을 만족시킬 수 있습니다.

이 과정을 코드로 작성해보겠습니다.

function buildHeap(heap) {
	for (let idx = Math.trunc((heap.length - 1) / 2); idx >= 0; idx--) {
		heapify(heap, idx);
	}
}

function heapify(heap, idx) {
	...
}

함수 heappush 가 큐에 데이터를 삽입하면서 우선 순위 큐를 만드는 기능이었다면 build_heap 은 삽입, 삭제 없이 배열의 요소들을 스왑함으로서 우선 순위 큐의 조건을 만족시킵니다. 새로운 큐 변수 없이 입력값 배열을 변형시키므로 별도의 메모리 공간을 필요로 하지 않습니다.



계층 별 노드들에 대해 heapify 를 실행하면 아래와 같은 연산 횟수를 보여줍니다.

전체 노드의 개수를 n 이라 할 때 각 계층의 노드 개수는 1, 2, 4, ..., n / 2 로 두 배씩 증가합니다. 스왑 연산 횟수는 log2nlog_2n 에서 하나씩 줄어 0에 도달합니다. 계층 별 연산 횟수를 합하면 다음과 같이 쓸 수 있습니다.

0⋅n2+1⋅n22+2⋅n23+3⋅n24+4⋅n25+...=n4(1+22+322+423+...)\begin{aligned} & 0 \cdot \frac{n}{2} + 1 \cdot \frac{n}{2^2} + 2 \cdot \frac{n}{2^3} + 3 \cdot \frac{n}{2^4} + 4 \cdot \frac{n}{2^5} + ... \\ \\ & = \frac{n}{4}(1 + \frac{2}{2} + \frac{3}{2^2} + \frac{4}{2^3} + ...) \end{aligned}

괄호 안의 식에서 더해지는 각 항은 분모는 지수 증가, 분자는 선형 증가하는 k2k−1\frac{k}{2^{k-1}} 형태입니다. kk 가 무한히 증가하면 (1+22+322+423+...)(1 + \frac{2}{2} + \frac{3}{2^2} + \frac{4}{2^3} + ...) 는 극솟값 수렴하므로 상수 치환할 수 있습니다. 합을 상수 cc 라 할 때 연산 횟수는 n4⋅c\frac{n}{4} \cdot c 입니다. 따라서 시간 복잡도는 O(n) 이라 할 수 있습니다.

상황에 맞게 heappush 대신 build_heap 을 이용하면 메모리도 절약하고 시간 복잡도도 낮출 수 있습니다.





출처 및 참고

자료구조
# 힙# 최대힙# 최소힙# 우선 순위 큐# javascript