그렇기 때문에 본 포스팅에서는 우선순위 큐를 구현하는 데 사용되는 힙의 개념을 설명한다. 힙의 필요성, 힙의 push, 힙의 pop 순으로 살펴보자.
위 그림의 우선순위 큐는 분명 큐인데 중간에 값의 위치가 바뀌는 일이 발생한다. 우선순위 큐가 "하나의 큐" 이상의 동작을 하는 것은 분명하다. 만약 직접 우선순위 큐를 구현한다면 어떤 방법으로 구현해야 할까?
단순한 방법을 생각해 보자.
우선순위별로 큐가 1개씩 존재하고, push 동작에서는 각 순위에 맞는 큐에 push 할 수 있다. pop 동작에서는 우선순위가 높은 큐부터 순회하며 원소를 1개 뽑을 때까지 순회한다.
위의 놀이공원 예시에서는 실제로 이러한 방법으로 동작하는 우선순위 큐이다. 하지만 이 방법은 치명적인 단점이 있는데. 우선순위의 레벨이 늘어나면 그만큼 여러 개의 큐를 준비해둬야 한다는 점이다.
놀이공원 같은 경우 2~3개 정도의 적은 레벨이기 때문에 크게 문제가 없다. 그런데 만약 응급실의 진료순서를 우선순위 큐로 나타낸다면 어떨까? 확실히 모든 환자를 순서대로 진료하기보다는 생명이 위급한 환자부터 진료를 하는 것이 맞을 것이므로 우선순위 큐로 나타내기엔 적합한 대상이다. 우리나라에는 응급환자 중증도를 5단계로 나누는 제도가 있으므로 5개의 큐를 만들면 될 것 같다. 여기에 감염병 (감염병도 등급에 따라 우선순위가 나뉠 수 있을 것 같다)이나 의료진이 사용하는 큐 등을 추가하면 8~9개는 넘어갈 수 있을 것 같다. 이런 식으로 아예 별도의 큐를 두는 방식은 레벨이 세분화될수록 전체 큐 개수도 늘어난다. 큐의 개수가 무한히 늘어난다면 그 큐들을 순회하는 것 자체가 점점 어려워진다.
이러한 우선순위 큐를 효율적으로 구현하기 위해 고안된 자료구조가 힙이며, 현재의 우선순위 큐 라이브러리는 거의 힙으로 구성되어 있다.
push 동작을 수행하는 우선순위 큐를 보며, 힙의 푸시를 설명하겠다.
새로운 노드가 삽입되면 항상 트리의 맨 끝에 추가한다, 현재 상태에서는 트리에 노드가 5밖에 없기 때문에 5의 왼쪽 자식으로 추가해 주었다.
이후 방금 삽입한 노드와 그 부모를 비교한다. 우선순위가 높은 노드일수록 root에 가깝도록 조정할 것이다. 만약 pop을 요청했을 경우 항상 루트의 값을 반환하게 처리할 것이다.
즉 현재 상태에서는 새로 들어온 1의 우선순위가 부모인 5보다 높기 때문에 둘을 교체한다. 교체된 이후에는 새로 들어온 1의 부모가 없기 때문에 종료, push가 끝난다.
조금 더 진행 한 뒤, 4가 삽입된 순간이다.
같은 규칙으로 4와 5는 교환되었다. 하지만 4의 부모보다 4의 우선순위가 낮기 때문에 1과 4의 교환은 이루어지지 않는다.
모든 노드를 삽입한 이후이다.
트리가 아닌 위쪽 큐를 보니 하나 이상한 점이 있다. 4보다 5가 앞에 있다는 점이다. 이것은 힙의 특징인 느슨한 정렬에 의해 나타난 현상이며, 실제 사용에는 지장이 없다. 느슨한 정렬이 상관없는 이유는 원소를 제거하는 부분에서 설명하도록 하겠다.
힙의 push는 비교적 간단하다. 그냥 맨 밑에서 시작하여 자기 부모와 비교하는 행위를 반복하면 된다.
pop 또한 구현은 간단하다, 하지만 push에 비하면 생각해 볼만한 포인트가 더 있다.
첫 번째는 위에서 언급된, 느슨한 정렬 개념이고.
두 번째는 하나의 원소를 pop 한 뒤, 빈 공간이 생긴다면 어떻게 할 것인지에 대한 부분이다.
먼저 느슨한 정렬부터 생각해보자 왜 push가 끝난 뒤의 큐 모양에서 4와 5의 순서가 바뀌어 있어도 괜찮은 것 일까?
push가 끝난 힙의 모양을 보면 위와 같은데, 검, 파, 빨 로 묶어놓은 모든 서브 트리에 대해서 "자식의 우선순위보다 부모의 우선순위가 높다"를 만족한다. 즉 모든 서브 트리를 힙이라고 불러도 틀리지 않다. (이러한 성질을 만족하기 위해 push 동작에서 삽입된 노드의 부모와 반복적인 비교를 했다.)
이것을 이렇게 생각해보자 1의 입장에서 잘은 모르겠지만 좌, 우측에 우선순위 큐가 존재한다. 잘은 모르겠지만 만약 1을 제거할 때엔 좌, 우측 우선순위 큐의 값 중 우선순위가 더 높은 값 에게 자기 자리를 물려준다.
근데 알고 보니 1의 왼쪽 우선순위 큐는?
알고보니 이렇게? 이렇게 돼있었던 것이다.
하지만 1의 입장에서는 왼쪽 우선순위 큐의 상태가 어떻든 그 우선순위 큐의 가장 우선순위가 높은 값 (= 루트) 에만 관심이 있다. 2의 오른쪽에 4가 있든, 왼쪽에 4가 있든 별 상관이 없다.
그래서 결론적으로 push 예시의 4와 5의 위치가 바뀌어 있어도 괜찮다.
모든 노드가 자기 부모보다만 우선순위가 낮게, 느슨하게 정렬되어 있어도 상관없는 이유를 보았다.
하지만 눈치 빠른 분들은 이것만으로는 충분하지 않다는 것을 알아챘을 것 같다.
위의 힙에서 1 노드를 그냥 pop 해버리고, 좌 우측 중 더 우선순위가 높은 것을 올리는 방법을 쓴다면
이렇게 4의 오른쪽 자식에 구멍이 뚫려버린다.
이렇게 되면 다음 값은 어디에 추가가 되어야 할까? 앞전 설명에서는 새로운 노드가 추가될 때엔 트리의 맨 끝에 추가한다는 규칙이었으니 3의 오른쪽에 추가해야 할까? 그렇게 마음을 먹으면 왠지 4 옆의 빈자리가 눈에 밟힌다.
그렇다고 4의 오른쪽에 값을 넣으려고 하면 이 힙이 매우 매우 커졌을 때, 빈자리를 찾는 동작 자체가 큰일이다.
그래서 힙에서는 맨 뒤의 원소를 루트와 교환하는 방식을 선택한다.
이후 맨 마지막 원소를 지워버린다면 정렬은 되지 않았을지언정, 구멍이 생기는 일은 발생할 수 없다. (참고로 msvc c++14 버전 기준으로 교체를 하고 있다, 개인적인 생각으로는 교체가 아닌 복사가 이루어지는 것이 조금 더 효율적이라 생각한다. 다른 언어, 다른 버전에서는 조금씩 다를 수 있다는 점을 유의 하자)
정렬이 깨져서 새롭게 정렬해야 하는 부분이 불편하게 느껴지는 사람이 있을지 모르겠다. 하지만 어차피 1이 그 자리에서 바로 사라지더라도 좌우측 자식 중 더 높은 우선순위를 가진 자식을 올리는, 새롭게 정렬하는 과정은 필요하다. 빈칸을 내리는 대신, 6을 내릴 뿐이다.
즉 올바른 방법으로 빈칸을 제거하는 pop 방식은
이렇게 된다.
그럼 한번 실제 예시에서의 pop을 따라가 보자
우선순위 큐 자체에 대한 개념과, 우선순위 큐 구현중 힙에 대한 내용을 살펴보았다.
지금은 거의 대부분 우선순위 큐 = 힙이라는 느낌이지만, 어떻게 바뀔지 모르기 때문에 (멀티 스레드 에서의 우선순위 큐도 과연 힙을 사용할까? 등) 각자 우선순위 큐에 대해 고민해보는 것은 좋을 것 같다.
지금까지의 자료구조 항목은 매우 기초적인 구조들이었기 때문에 굳이 구현을 첨부하지는 않았다.
하지만 이후에 하나하나 올릴 내용들은 여러 가지로 응용이 가능한 기본기 이긴 하지만 구현이(최소한 스택만큼) 간단하지 않다고 생각하여 간단한 구현 코드를 첨부하기로 했다. (코드에 대한 질문이나 불합리 사항은 댓글로...)
