우선순위 큐의 이해
우선순위 큐는 그 이름이 의미하듯이 큐와 관련이 있다. 하지만 공부하다 보면 그 관계가 깊지 않다고 느낄수도 있다. 제목만 봐서는 앞서 구현한 '큐'를 확장하는 수준에서 마무리가 될것 같지만 '큐'의 구현과 우선순위 큐'의 구현에는 많은 차이가 있기 때문이다.
우선순위 큐와 우선순위의 이해
큐의 핵심연산 두 가지는 다음과 같다.
enqueue : 큐에 데이터를 삽입하는 행위
dequeue : 큐에서 데이터를 꺼내는 행위
이와 마찬가지로 '우선순위 큐'의 핵심 연산 두 가지도 다음과 같다.
enqueue : 우선순위 큐에 데이터를 삽입하는 행위
dequeue : 우선순위 큐에서 데이터를 꺼내는 행위
반면 연산의 결과에는 차이가 있다. 큐는 연산의 결과로, 먼저 들어간 데이터가 먼저 나오지만, 우선순위 큐의 연산결과는 다음과 같다.
"들어간 순서에 상관 없이 우선순위가 높은 데이터가 먼저 나온다."
때문에 큐를 가리켜 '줄서기'에 비유한다면, 우선순위 큐는 '응급상황'에 비유할 수 있다. 예를 들어 병원의 응급실을 생각해보면, 다음과 같이 크게 두 부류로 나눌 수 있을 것이다.
응급상황 1 : 촌각을 다투는, 생명이 위급한 상황의 환자
응급상황 2 : 촌각을 다투지는 않지만 내일 까지 기다리기에는 무리인 환자.
즉 우선순위가 높은 환자가 먼저 치료받는 것이다. 이렇듯 우선순위 큐에서 중요한 것은 우선순위이다.
데이터를 근거로 우선순위를 판단할 수 있어야 한다. 물론 우선순위의 판단 근거는 프로그래머가 결정할 일이다. 즉 목적에 맞게 우선순위를 결정하면 된다.
우선 순위 큐의 구현 방법
우선순위 큐를 구현하는 방법은 다음과 같이 세 가지로 구분할 수 있다.
1. 배열을 기반으로 구현하는 방법
2. 연결리스트를 기반으로 구현하는 방법
3. 힙(heap)을 이용하는 바업
배열이나 연결리스트를 이용하면 우선순위 큐를 매우 간단히 구현할 수 있다.
배열의 경우, 데이터의 우선순위가 높을수록 배열의 앞쪽에 데이터를 위치시킨다. 이렇게 하면 우선순위가 높은 데이터를 반환 및 소멸하는 것은 어려운 일이 아니다. 하지만 우리도 알다시피 다음과 같은 단점이 따른다.
"데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야 한다."
이는 배열의 대표적인 단점이다. 하지만 이보다 더 큰 문제는 다음과 같다.
"삽입의 위치를 찾기 위해서 배열에 저장된 모든 데이터와 우선순위의 비교를 진행해야 할 수 있다."
이는 우선순위가 가장 낮은 데이터를 저장하는 경우에 발생하는 최악의 상황이다. 하지만 최악의 상황이 아니더라도 이와 유사한 좋지 않은 상황은 빈번히 발생한다. 그렇다면 연결 리스트의 경우는 어떨까? 연결 리스트의 경우, 위에서 말한 배열의 첫 번째 단점은 갖지 않는다. 하지만 두 번째 단점은 연결 리스트에도 존재한다.
"삽입의 위치를 찾기 위해서 첫 번째 노드에서부터 시작해서 마지막 노드에 저장된 데이터와 우선순위의 비교를 진행해야 할 수 있다."
이는 데이터의 수가 적은 경우 큰 단점이 되지 않을 수 있다. 하지만 데이터의 수가 많아지면 , 그래서 연결된 노드의 수가 많아지면, 노드의 수에 비례해서 성능을 저하시키는 주 원인이 된다. 그래서 우선순위큐는 단순 배열도 연결 리스토도 아닌 '힙'이라는 자료구조를 이용해서 구현하는 것이 일반적이다.
힙(Heap)의 소개
힙은 이진트리이되 완전 이진 트리 이다. 그리고 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다. 즉 루트 노드에 저장된 값이 가장 커야한다.
위에서 말하는 '값'은 말 그대로 '값'이 될 수도 있고, 우선순위 큐에서 말하는 '우선순위'가 될 수도 있다. 그런데 우리는 힙을 기반으로 우선순위 큐를 구현할 계획을 갖고 있으니, 위 문장의 '값'은 '우선순위'가 된다. 그럼 위의 문장에서 말하는 형태의 이진 트리를 그림으로 그리겠다.
위와 같이 루트 노드로 올라갈수록 저장된 값이 커지는 완전 이진 트리를 가리켜 '최대 힙(max heap)'이라 한다. 반면 다음 그림과 같이 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리를 가리켜 '최소 힙(min heap)'이라 한다.
이렇듯 힙은 루트 노드에 우선 순위가 가장 높은 데이터를 위치시킬 수 있는 자료구조이니, 이를 기반으로 하면 우선순위 큐를 간단히 구현할 수 있지 않겠는가?? 참고로 위의 두 그림에서 보이듯이, 힙은 무언가를 쌓아 놓은 더미와 흡사하다 하여 지어진 이름이다. 영단어 heap은 '무엇인가를 차곡차곡 쌓아 올린 더미'라는 뜻을 지닌다.
힙의 구현과 우선순위 큐의 완성
힙의 구현은 곧 우선순위의 큐의 완성으로 이어진다. 따라서 힙과 우선순위 큐를 동일하게 인식하는 경향이 매우 강하다. 하지만 이는 정확하지 않은 것이니, 우선순위 큐와 힙을 어느 정도 구분을 해야한다.
힙은 우선순위 큐의 구현에 딱 어울리는, 완전 이진 트리의 일종이라는 사실을 기억해야 한다.
힙에서의 데이터 저장과정
힙을 구현하고 이를 기반으로 우선순위 큐를 구현하고자 한다. 그런데 힙의 구현을 위해서는 데이터의 저장과 삭제의 방법을 먼저 알아야 한다. 따라서 먼저 데이터의 저장과정을 '최소 힙'을 기준으로 설명한다.
위 그림에서 쓰여 있는 숫자를 데이터 겸 우선순위라 하자. 그리고 숫자가 작을수록 우선순위가 높다고 가정하자. 그렇다면 위의 그림은 우선순위 관점에서 힙이 맞다. 완전 이진 트리이면서, 어느 위치에서든 다음식이 성립하기 때문이다.
자식 노드 데이터의 우선 순위 <= 부모 노드 데이터의 우선순위
그럼 위 그림의 상황에서 3을 저장한다고 가정해보자. 물론 저장한 이후에도 트리의 우선순위 관계를 유지시키는 것이 관건이다. 그런데 이것이 생각보다 쉽지 않다. 딱 보는 순간 문제의 해결을 위한 알고리즘이 떠오르지는 않을 것이다. 따라서 먼저 전략을 제시하겠다.
"새로운 데이터는 우선순위가 제일 낮다는 가정하에 '마지막 위치'에 저장한다. 그리고는 부모 노드와 우선순위를 비교해서 위치가 바뀌어야 한다면 바꿔준다. 바뀐 다음에도 계속해서 부모 노드와 비교한다. 제대로된 위치를 찾을 때 까지."
위의 문장에서 말하는 '마지막 위치'는 노드를 추가한 이후에도 완전 이진 트리가 유지되는, 마지막 레벨의 가장 오른쪽 위치를 뜻한다. 앞으로도 우리는 이 위치를 '마지막 위치'로 표현할 것이다.
이제 숫자 3을 추가하기 위한 첫번째 단계를 보이겠다.
위 그림과 같이, 마지막 위치에 노드를 추가하고 부모 노드와 우선순위를 비교한다. 그 결과 이 둘은 서로 위치ㅏ 바뀌어야 한다. 따라서 다음 그림과 같이 두 노드의 위치를 바꾼 다음에, 이어서 다시 부모 노드와의 비교를 진행한다.
이번에도 부모 노드의 우선순위가 낮으니, 다음 그림과 같이 두 노드를 바꾼 다음에, 마지막으로 루트노드와의 비교를 진행해야 한다.
그런데 이번에는 부모 노드보다 우선순위가 높지 않으니 , 이로써 숫자 3은 자신의 위치를 찾은 셈이다. 이제 위 그림의 우선순위를 관찰하자. 이 그림이 숫자 3을 추가한 최종 결과인데, 여전히 힙의 조건을 만족하고 있음을 알 수 있다.
이렇듯 데이터의 추가과정은 마지막 위치에 데이터를 두고서 부모 노드와의 비교를 통해 자신의 위치를 찾아가는 매우 단순한 방식이다.
힙에서의 데이터 삭제 과정
이번에는 삽입보다 어려울 것으로 생각되는, 하지만 실제로는 삽입과 비슷한 '삭제의 과정'을 고민할 차례이다. 그런데 그에 앞서 무엇을 삭제할 것인지 생각해보자. 우리는 우선순위 큐의 구현을 위해서 힙을 활용할 계획을 갖고 있다. 그런데 우선순위 큐의 삭제는 '가장 높은 우선순위의 데이터 삭제'를 의미하므로, 우리는 힙을 대상으로 다음 내용을 고민해야 한다.
"힙에서 루트 노드를 어떻게 삭제할 것인가?"
물론 루트 노드를 삭제하는 것은 어렵지 않다. 문제는 삭제 후에도 힙의 구조를 유지해야 한다는데 있다. 즉 우리가 고민해야 할 문제의 본질은 다음과 같다.
"힙에서 루트 노드를 삭제한 다음에 이 부분을 어떻게 채울 것인가?"
다음 그림을 보면서 , 이 문제를 어떻게 해결할 것인지 그 해결책을 우리가 먼저 고민해보 자. 앞서 보인 삽입의 방법에서 힌트를 얻을 수 있을 것이다.
그럼 이어서 이 문제의 전통적인 해결책을 설명하겠다. 참고로 아래의 문장에서 말하는 '마지막 노드'는 완전 이진트리에서 마지막 레벨의 가장 오른쪽에 위치한 노드를 뜻한다.
"마지막 노드를 루트 노드의 자리로 옮긴 다음에, 자식 노드와의 비교를 통해서 제자리를 찾아가게 한다."
제자리를 찾아가게 한다는 점에서 삽입의 방법과 유사한 방법이라는 느낌이 든다. 그럼 위의 문장에서 말하는 해결책을 따라가 보겠다. 일단 첫 번째 단계로 힙의 마지막 노드를 루트 노드의 위치로 이동시킨다.
이어서 노드를 삽입할 때와 유사하게, 비교의 과정을 통해서 8이 제 위치를 찾게끔 한다. 즉 다음 그림에서 보이듯이 두 개의 자식 노드 중 우선순위가 높은 3이 저장된 왼쪽 자식노드와 8이 저장된 노드를 교환한다. 물론 이 과정에서 오른쪽 자식 노드의 우선순위가 높다면, 오른쪽 자식 노드와 교환해야 한다.
참고로 우선순위가 낮은 자식 노드와 교환하면 안되는 이유는, 그렇게 했을 경우 힙의 기본 조건이 무너지기 때문이다. 이어서 숫자 8은 자식 노드와 비교를 진행한다. 4와 9중에서 우선순위가 높은 4와 비교를 진행한다. 그 결과 4가 8보다 우선순위가 높으니 다음 그림과 같이 교환을 진행한다.
위 그림에서 8이 저장된 노드도 자식 노드가 존재하는 관계로 비교를 진행해야 한다. 그러나 우선순위가 8이 높은 관계로 이 상태에서 빈 공간을 채우는 과정은 마무리가 된다.
삽입과 삭제의 과정에서 보인 성능의 평가
힙에 대한 이론적인 설명이 일단락 되었으니 다음 질문에 답을 해보자.
"우선순위 큐의 구현에 있어서 단순 배열이나 연결리스트 보다 힙이 더 적합한 이유는 어디에 있는가?"
앞서 언급한, 데이터의 우선순위가 높을수록 데이터를 배열의 앞쪽에 위치시키는 방식으로 구현한 우선순위 큐의 성능은 다음과 같이 정리할 수 있다.
배열 기반 데이터 저장의 시간 복잡도 O(n)
배열 기반 데이터 삭제의 시간 복잡도 O(1)
우선순위가 낮은 데이터를 배열에 저장하는 경우, 배열에 저장된 모든 데이터와의 우선순위 비교과정을 거쳐야 하므로 데이터 저장의 시간 복잡도는 O(n)이 되고, 삭제의 과정에서는 맨 앞에 저장된 데이터를 삭제하면 되기 때문에, 이 경우의 시간 복잡도는 O(1)이 된다. 이와 유사하게 , 앞서 언급한 연결 리스트 기반의 우선운위 큐의 성능도 다음과 같이 정리할 수 있다.
연결 리스트 기반 데이터 저장의 시간 복잡도 O(n)
연결 리스트 기반 데이터 삭제의 시간 복잡도 O(1)
우선순위가 높을수록, 데이터를 연결 리스트의 앞 부분에 배치하는 방식으로 배열의 경우와 다를 바가 없다. 하지만 힙의 경우는 어떤가? 삽입이나 삭제의 경우 동반되는 비교연산은 주로 부모 노드와 자식 노드 사이에서 일어난다. 그리고 이것이 의미하는 바는 다음과 같다.
"힙을 기반으로 하면 트리의 높이에 해당하는 수만큼만 비교연산을 진행하면 된다"
이는 트리의 높이가 하나 늘어날 때마다 비교연산의 횟수가 하나 증가한다는 뜻이므로, 힙의 성능은 다음과 같이 정리할 수 있다.
힙 기반 데이터 저장의 시간 복잡도 O(log_2 n);
힙 기반 데이터 삭제의 시간 복잡도 O(log_2 n);
힙은 완전 이진 트리이므로, 힙에 저장할 수 있는 데이터의 수는 트리의 높이가 하나 늘 때마다 두 배씩 증가한다. 때문에 데이터의 수가 두 배 늘 때마다, 비교연산의 횟수는 1회 증가한다. 바로 이 사실을 근거로 위의 결론을 내릴 수 있다.
이로써 우선순위 큐에 구현에 있어서 배열보다 연결 리스트보다도 힙이 어울리는 이유를 객관적으로 정리하였다.
힙의 구현에 어울리는 것은 연결 리스트? 아니면 배열?
우선순위 큐의 구현에 어울리는 것은 힙으로 결론이 났으니, 이제는 힙의 구현방법에 대해서 고민해야 한다. 그런데 힙은 트리이다. 앞서 트리를 구현하는 방법에는 '배열'을 이용하는 방법과 '연결 리스트'를 이용하는 방법이 있음을 설명하였으니, 배열과 연결 리스트 중 하나를 선택해야 한다.
"앞서 연결 리스트를 기반으로 트리를 구현하였으니, 당연히 연결 리스트를 힙의 구현 도구로 선택해야한다."
하지만 우리의 생각과 달리 완전 이진 트리의 구조를 갖고 또 구조를 유지해야 하는 '힙'은 배열 기반으로 구현해야 한다.
실제로 힙의 구현은 배열 기반으로 구현하는 것이 원칙으로 여겨지고 있는데, 그 이유는 다음과 같다.
"연결 리스트를 기반으로 힙을 구현하면, 새로운 노드를 힙의 '마지막 위치'에 추가하는 것이 쉽지 않다."
사소한 이유 같고, 그래서 연결 리스트를 기반으로도 쉽게 해결 가능한 문제처럼 보이지만, 이는 결코 간단한 문제가 아니다. 하지만 배열 기반의 힙이라면 이는 매우 간단한 문제가 된다. 그래서 힙과 같이 새로운 노드를 추가한 이후에도 완전 이진트리를 유지해야 하는 경우에는 연결 리스트가 아닌 배열을 기반으로 트리를 구현해야 한다.
'휴지통 > 자료구조-C' 카테고리의 다른 글
| 우선순위 큐(Priority Queue) 와 힙(Heap) 2 (0) | 2021.03.08 |
|---|---|
| 트리2 (0) | 2021.03.03 |
| 트리 1 (0) | 2021.03.02 |
| 덱(Deque)의 이해와 구현 (0) | 2021.03.01 |
| 큐(Queue)의 연결리스트 기반 구현 (0) | 2021.02.28 |
