자바스크립트로 우선순위 큐 만들기

겨울 참새. Unsplash에 Marcos Paulo Prado님이 올림.

들어가는 말

이 글은 자바스크립트로만 알고리즘 코딩 테스트를 준비하는 분들을 위한 글입니다.

다른 언어가 사용 가능하다면(특히 파이썬) 그걸 쓰는 게 훨씬 좋아요. 하지만 자바스크립트로 코딩 테스트를 준비하신다면 우선순위 큐 구현법은 꼭 알아야 합니다. 일부 그리디 유형의 문제를 풀거나 프림, 다익스트라 알고리즘을 사용할 때 우선순위 큐가 필요하거든요.

이 글에서는 우선순위 큐를 구현하는 기본적인 원리와 파이썬에서 우선순위 큐를 구현하는 방법을 알아보고 각각에 대한 코드 예시를 첨부할 예정입니다.

우선순위 큐란?

자료를 빼낼 때 들어온 순서에 상관없이 우선순위 큐 내부의 값들 중 가장 우선순위가 높은 친구가 먼저 나오는 자료구조에요. 보통 힙(Heap)으로 구현합니다.

우선순위 큐 ≠ 힙

힙은 우선순위 큐의 구현체 중 하나일 뿐이지 모든 우선순위 큐는 힙이 아닙니다.

힙이란?

완전 이진 트리 형태의 자료구조입니다. 어떤 노드의 자식들은 절대 본인보다 우선순위가 높을 수 없으며, 자식 중 어떤 자식이 우선순위가 높은지 역시 알 수 없어요. 또한 올바른 힙 내부에서 무작위로 한 점을 뽑아 루트로 하더라도 그 하위 트리는 전부 힙이에요.

완전 이진 트리란?

이진 트리인데 마지막이 아닌 각 가로층이 앞에서부터 꽉꽉 채워져 있는 형태입니다. 위 사진처럼 앞에서부터 꽉 채워서 표현하기 때문에 배열로 구현이 가능해요.

이진 트리란?

트리인데 자식이 항상 둘 이하인 트리에요.

트리란?

사이클이 없는 그래프에요.

우선순위 큐를 힙으로 구현할 수 있는 이유

힙에서 어떤 노드의 자식들은 절대 본인보다 우선순위가 높을 수 없기 때문에, 힙의 가장 뿌리에 있는 값은 항상 가장 큰 우선순위를 가집니다. 이 특징을 사용하면 우선순위 큐를 힙으로 표현할 수 있어요.

최대 힙 구현하기

배열과 힙

힙은 완전 이진 트리니까 배열을 이용해서 구현이 가능해요.

사진처럼 루트 노드를 1번 index로 해서 쭉쭉 나갈 수 있습니다. 핵심은 두 가지에요.

루트는 1번
왼쪽 자식은 본인 * 2, 오른쪽 자식은 본인 * 2 + 1

힙에 새로운 값 추가하기

1. 배열 맨 뒤에 넣기

힙에 새로운 값을 넣는 법은 간단합니다.

이렇게 생긴 최대 힙에 40을 넣어봅시다.

먼저 배열 맨 뒤에 새로운 값을 넣습니다. 이진 트리니까 빈자리 없이 넣어야 하므로 맨 뒤에 바로 붙여야 해요.

2. 부모 끌어내리기

근데 이러면 문제가 있어요. 노드의 자식들은 본인보다 우선순위가 높아서는 안 되는데, 12의 자식인 40이 훨씬 우선순위가 높습니다. 이러면 자연계의 대법칙인 약육강식의 논리를 사용해서 12를 끌어내리면 됩니다.

이러면 40의 자식이 8과 12로 올바른 힙 모양을 만들 수 있어요.

하지만 40 입장에서는 본인의 새로운 부모인 30도 마음에 들지 않아요. 또 끌어내립니다.

40은 50보다 우선순위가 낮으므로 40의 유쾌한 반란은 여기까지입니다.

어떤 값이 주어졌을 때 바로 위 부모와의 우선순위를 비교하여 본인의 우선순위가 높다면 부모를 끌어내리고 본인을 부모 위치로 보내는 것. 이 과정을 저는 '부모 끌어내리기'라고 불러요. 보통은 'bubble up'이라고 많이 하고, 파이썬은 'sift down'이라고 표현합니다.

같은 방법으로 77을 넣어 봅시다.

먼저 배열 맨 뒤에 넣고,

본인이 부모보다 우선순위가 높다면 부모를 쭉 끌어내립니다

이 경우에는 77이 가장 큰 값이니까 맨 꼭대기까지 올라갔네요.

힙에서 값 빼기

1. 배열 맨 앞의 값 없애기

우선순위 큐는 가장 우선순위가 높은 것부터 제거합니다. 힙의 맨 꼭대기에는 가장 우선순위가 높은 값이 들어 있으므로 이 값을 없애요.

2. 배열 맨 뒤의 값을 맨 앞으로 옮기기

빈 공간을 채워야겠죠? 배열 맨 뒤의 값을 제거해서 맨 앞에 넣어줍니다.

3. 자식 끌어올리기

만들어진 트리의 모양을 보면 4보다 우선순위가 한참 높은 50과 44가 자식에 있기 때문에 올바른 힙이 아니에요. 이제 4를 제자리로 보내야 합니다.

보내는 방법은 간단해요. 본인보다 우선순위가 높은 자식에게 자기 자리를 양보하면 됩니다. 두 자식 중 더 우선순위가 높은 50을 끌어올립니다.

두 자식 중 더 우선순위가 높은 친구를 올리는 이유는, 더 낮은 걸 올린다면 어차피 힙이 깨져서 다시 더 큰 자식을 올려야 하기 때문이에요.

마찬가지로 30과 40 중 더 큰 자식인 40에게 자리를 양보합니다. 이러면 4에게는 더 이상 자식이 없고, 힙도 정상적인 모양으로 돌아오게 됩니다.

트리의 맨 꼭대기부터 본인보다 우선순위가 높은 자식을 끌어올리는 것을 저는 ‘자식 끌어올리기’라고 불러요. ‘bubble down’이 더 일반적인 표현입니다.

같은 방법으로 맨 앞의 요소를 다시 빼 볼까요?

먼저 50을 빼고,

맨 뒤의 12를 맨 앞으로 옮긴 다음

자식 끌어올리기를 통해 제자리로 보내면 됩니다.

실제 구현

코드 보러가기

백준 11279번 문제,'최대 힙'을 위에서 설명한 방법대로 구현한 코드에요.

부모와 자식 '바꿔치기'에 드는 비용을 생각해서 실제로 바꿔치지는 않고, 최종적으로 값이 들어가야 하는 위치만 바꾸는 식으로 구현했어요.

배열의 0번 인덱스를 비워둔 이유는 부모 자식 계산을 할 때 1번 인덱스를 루트로 하는 게 저는 더 편해서에요.

파이썬 식으로 최대 힙 구현하기

파이썬은 뭐가 다르길래

파이썬은 힙에서 값을 뺄 때 조금 다른 방식을 사용해요.

앞서 우리는 배열 맨 뒤의 값을 맨 앞으로 옮긴 다음 자식 끌어올리기를 진행했는데요. 생각해 보면 배열 맨 뒤의 값은 필연적으로 우선순위가 상당히 낮을 텐데, 그걸 굳이 맨 앞에 넣을 필요가 있을까요? 본인과 자식 두 명까지 총 세 개의 값을 비교하는 건 과할 수 있겠다는 생각이 들지도 모릅니다.

그래서 파이썬은 배열 맨 뒤의 값을 맨 앞으로 보내지 않아요. 대신 빈 자리는 자식 둘이 경쟁해서 더 우선순위가 높은 아이가 올라옵니다. 그렇게 해서 트리의 리프 노드가 빌 때까지 빈 자리를 채워요. 그리고 그 빈 자리에 배열 맨 뒤의 값을 넣고 거기서부터 부모 끌어내리기를 진행합니다.

이 부분을 파이썬이 어떻게 설명했는지 궁금하시다면 실제 파이썬 코드의 주석을 읽어보세요!