우선순위 큐의 이해
우선순위 큐와 우선순위의 이해
큐의 핵심 연산은 큐에 데이터를 삽입하는 행위와 큐에서 데이터를 꺼내는 행위입니다. 이와 마찬가지로 우선순위 큐의 핵심 연산은 우서눈위 큐에 데이터를 삽입하는 행위와 우선순위 큐에서 데이터를 꺼내는 행위입니다. 반면 연산의 결과에는 차이가 있습니다. 큐는 연산의 결과로, 먼저 들어간 데이터가 먼저 나오지만, 우선순위 큐의 연산결과는 다음과 같습니다. 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나옵니다. 우선순위 큐는 응급상황에 비유할 수 있습니다. 우선순위를 지녀야 한다기 보다는, 데이터를 근거로 우선순위를판단할 수 있어야 합니다. 우선순위의 판단 근거는 프로그래머가 결정할 일입니다. 즉 목적에 맞게 우선순위를 결정하면 됩니다.
우선순위 큐의 구현 방법
배열을 기반으로 구현하는 방법과 연결 리스트를 기반으로 구현하는 방법 그리고 힙을 이용하는 방법이 있습니다. 배열이나 연결 리스트를 이용하면 우선순위 큐를 매우 간단히 구현할 수 있습니다. 배열의 경우, 데이터의 우선순위가 높을수록 배열의 앞쪽에 데이터를 위치시킵니다. 우선순위가 높은 데이터를 반환 및 소멸하는 것이 어려운 일이 아닙니다. 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야 합니다. 삽입의 위치를 찾기 위해서 배열에 저장된 모든 데이터와 우선순위의 비교를 진행해야 할 수도 있습니다. 삽입의 위치를 찾기 위해서 첫 번째 노드에서부터 시작해서 마지막 노드에 저장된 데이터와 우선순위의 비교를 진행해야 할 수도 있습니다.
힙의 소개
힙이라는 자료구조를 이요해서 우선순위 큐를 구현하고자 합니다. 힙은 이진 트리이되 완전 이진 트리입니다. 그리고 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 합니다. 즉 루트 노드에 저장된 값이 가장 커야 합니다. 힙을 기반으로 우선순위 큐를 구현할 계획을 갖고 있으니, 위 문장의 값은 우선순위가 됩니다. 루트 노드로 올라갈수록 저장된 값이 커지는 완전 이진 트리를 가리켜 최대 힙이라고 합니다. 반면 다음 그림과 같이 루트 노드로 올라갈수록 저장된 값이 작아지는 완전 이진 트리를 가리켜 최소 힙이라고 합니다. 영단어 힙은 무엇인가를 차곡차곡 쌓아 올린더미라는 뜻입니다.
힙의 구현과 우선순위 큐의 완성
힙의 구현은 우선순위 큐의 완성으로 이어집니다. 힙은 우선순위 큐의 구현에 어울리는, 완전 이진 트리의 일종이라는 사실을 기억하기 바랍니다.
힙에서의 데이터 저장과정
힙을 구현하고 이를 기반으로 우선순위 큐를 구현하고자 합니다. 새로운 데이터는 우선순위가 제일 낮다는 가정하에서 마지막 위치에 저장합니다. 그리고는 부모 노드와 우선순위를 비교해서 위치가 바뀌어야 한다면 바꿔줍니다. 바뀐 다음에도 계속해서 부모 노드와 비교합니다. 제대로 된 위치를 찾을 때까지 말입니다. 마지막 위치는 노드를 추가한 이후에도 완전 이진 트리가 유지되는, 마지막 레벨의 가장 오른쪽 위치를 뜻합니다. 데이터의 추가 과정은 마지막 위치에 데이터를 두고서 부모 노드와의 비교를 통해 자신의 위치를 찾아가는 매우 단순한 방식입니다.
힙에서의 데이터 삭제 과정
우선순위 큐의 삭제는 가장 높은 우선순위의 데이터 삭제를 의미합니다. 힙에서 루트 노드를 어떻게 사용할 것인가요. 마지막 노드를 루트 노드의 자리로 옮긴 다음에, 자식 노드와의 비교를 통해서 제자리를 찾아가게 합니다.
삽입과 삭제의 과정에서 보인 성능의 평가
우선순위 큐의 구현에 있어서 단순 배열이나 연결 리스트보다 힙이 더 적합한 이유는 어디에 있나요. 배열 기반 데이터 저장의 시간 복잡도는 O(n) 이고 배열 기반 데이터 삭제의 시간 복잡도는 O(1) 입니다. 우선순위가 낮은 데이터를 배열에 저장하는 경우, 배열에 저장된 모든 데이터와의 우선순위 비교과정을 거쳐야 하므로 데이터 저장의 시간 복잡도는 O(n)이 되고, 삭제의 과정에서는 맨 앞에 저장된 데이터를 삭제하면 되기 때문에, 이 경우의 시간 복잡도는 O(1)이 됩니다. 연결 리스트 기반 데이터 저장의 시간 복잡도, 연결 리스트 기반 데이터 삭제의 시간 복잡도. 힙을 기반으로 하면 트리의 높이 해당하는 수만큼만 비교연산을 진행하면 됩니다. 트리의 높이가 하나 늘어날 때마다 비교연산의 횟수가 하나 증가한다는 뜻이므로, 힙의 성능은 다음과 같이 정리할 수 있습니다. 힙 기반 데이터 저장의 시간 복잡도, 힙 기반 데이터 삭제의 시간 복잡도.
힙의 구현에 어울리는 것은 연결 리스트? 아니면 배열?
앞서 연결 리스트를 기반으로 트리를 구현하였으니, 당연히 연결 리스트를 힙의 구현 도구로 선택해야겠습니다. 아닙니다. 완전 이진 트리의 구조를 갖고 또 그 구조를 유지해야 하는 힙은 배열을 기반으로 구현해야 합니다. 연결 리스트를 기반으로 힙을 구현하면, 새로운 노드를 힙의 마지막 위치에 추가하는 것이 쉽지 않습니다.
배열을 기반으로 힙을 구현하는데 필요한 지식들
노드에 고유의 번호를 부여합니다. 그리고 그 번호가 각 노드의 데이터가 저장 될 배열의 인덱스 값이 됩니다. 왼쪽 그리고 오른쪽 자식 노드의 인덱스 값을 얻는 방법, 그리고 부모 노드의 인덱스 값을 얻는 방법. 이진 트리는 레벨이 증가함에 따라서 추가할 수 있는 노드의 수가 두 배씩 증가하는 구조다 보니, 2를 나누고 곱하는 방식으로 부모 노드와 자식 노드의 인덱스 값을 구할 수 있습니다.
원리 이해 중심의 힙 구현: 헤더파일의 소개
힙에 저장될 데이터의 모델을 정의한 구조체이비낟.
원리 이해 중심의 힙 구현 : HDelete 함수에 대한 설명 중심으로
힙은 완전하 이진 트리입니다. 힙의 구현은 배열을 기반으로 하며 인덱스가 0인 요소는 비워둡니다. 따라서 힙에 저장된 노드의 개수와 마지막 노드의 구유번호는 일치합니다. 노드의 고유번호가 노드가 저장되는 배열의 인데스 값이 됩니다. 우선순위를 나타내는 정수 값이 작을수록 높은 우선순위를 나타낸다고 가정합니다.
함수 GetHiPriChildIDX에 노드의 인덱스 값을 전달하면, 이 노드의 두 자식 노드 중에서 우선순위가 높은 것의 인덱스 값을 반환합니다. 함수 GetHiPriChildIDX는 인자로 전달된 노드에 자식 노드가 없으면 0을 반환하고, 자식 노드가 하나인 경우에는 그 노드의 인덱스 값을 반환합니다.
#include "SimpleHeap.h" void HeapInit(Heap * ph) { ph->numOfData = 0; } int HIsEmpty(Heap * ph) { if (ph->numOfData == 0) return TRUE; else return FALSE; } // parent node index value return int GetParentIDX(int idx) { return idx / 2; } // left kid node index value return int GetLChildIDX(int idx) { return idx * 2; } // right kid node index value return int GetRChildIDX(int idx) { return GetLChildIDX(idx) + 1; } //two kid node priority node index value return int GetHiPriChildIDX(Heap * ph, int idx) { if (GetLChidIDX(idx) > ph->numOfData) return 0; else if (GetLChildIDX(idx) == ph->numOfData) return GetLChildIDX(idx); else { if (ph->heapArr[GetLChildIDX(idx)].pr > ph->heapArr[GetRChildIDX(idx)].pr ) return GetRChildIDX(idx); else return GetLChildIDX(idx); } } // in Heap save data void HInsert(Heap * ph, HData data, Priority pr) { int idx = ph->numOfData + 1; HeapElem nelem = { pr, data }; while (idx != 1) { if (pr < (ph->heapArr[GetParentIDX(idx)].pr)) { ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)]; idx = GetParentIDX(idx); } else break; } ph->heapArr[idx] = nelem; ph->numOfData += 1; } // in Heap delete data HData HDelete(Heap * ph) { HData retData = (ph->heapArr[1]).data; HeapElem lastElem = ph->heapArr[ph->numOfData]; int parentIdx = 1; int childIdx; while (childIdx = GetHiPriChildIDX(ph, parentIdx)) { if (lastElem.pr <= ph->heapArr[childIdx].pr) break; ph->heapArr[parentIdx] = ph->heapArr[childIdx]; parentIdx = childIdx; } ph->heapArr[parentIdx] = lastElem; ph->numOfData -= 1; return retData; } |
힙은 완전 이진 트리이므로 오른쪽 자식 노드만 존재하는 상황은 발생하지 않습니다. 따라서 왼쪽 자식 노드가 없다면 자식 노드가 존재하지 않는 것으로 판단할 수 있습니다. 자식 노드가 하나도 존재하지 않는 노드는 단말 노드입니다. 하나뿐인 자식 노드는 왼쪽 자식 노드입니다. 그리고 힙의 마지막 노드입니다. 힙의 마지막 노드를 루트 노드의 위치에 올린 다음에, 자식 노드와의 비교과정을 거치면서 아래로 내립니다. 자신의 위치를 찾을 때까지 내립니다. 루트 노드로 올려진 마지막 노드는 자신의 위치를 찾을 때까지 아래로 이동하면서 자신의 위치를 찾아갑니다.
함수 HDelet 에서는 마지막 노드가 있어야 할 위치를 parentIdx 에 저장된 인덱스 값을 갱신해가며 찾아가고 있습니다.
원리 이해 중심의 힙 구현: Hinsert 함수에 대한 설명 중심으로
새로운 데이터는 우선순위가 제일 낮다는 가정하에서 마지막 위치에 저장합니다. 그리고는 우선순의 비교를 통해서 자신의 위치를 찾을 때까지 위로 올립니다.
완성한 힙의 실행을 위한 main 함수
#include <stdio.h> #include "SimpleHeap.h" int main(void) { Heap heap; HeapInit(&heap); HInsert(&heap, 'A', 1); HInsert(&heap, 'B', 2); HInsert(&heap, 'C', 3); printf("%c \n", HDelete(&heap)); HInsert(&heap, 'A', 1); HInsert(&heap, 'B', 2); HInsert(&heap, 'C', 3); printf("%c \n", HDelete(&heap)); while (!HIsEmpty(&heap)) printf("%c\n", HDelete(&heap)); return 0; } |
실행결과는 우선순위가 높은 문자들이 먼저 꺼내졌음을 증명하고 있습니다.
쓸만한 수준의 힙 구현: 힙이 변경
프로그래머가 우선순위의 판단 기준을 힙에 설정할 수 있어야 합니다. HeapElem은 데이터와 우선순위를 하나로 묶기 위한 구조체였는데, 이 중에서 우선순위를 저장하는 멤버를 완전히 없앴기 때문에 더 이상 존재할 이유가 사라진 것입니다. 이는 함수 포인터 변수입니다. 두 개의 데이터를 대상으로 우선순위의 높고 낮음을 판단하는 함수를 등록하기 위한 포인터 변수입니다. PriorityComp의 typedef 선언은 다음과 같습니다. typedef int PriorityComp, 첫 번째 인자의 우선순위가 높다면, 0보다 큰 값이 반환되도록 정의합니다. 두 번째 인자의 우선순위가 높다면, 0보다 작은 값이 반환되도록 정의합니다. 첫 번째, 두 번째 인자의 우선순위가 동일하다면, 0이 반환되도록 정의합니다.
힙의 변경 사항 완성하기
#include <stdio.h> #include "UsefulHeap.h" int DataPriorityComp(char ch1, char ch2) { return ch2 - ch1; } int main(void) { Heap heap; HeapInit(&heap, DataPriorityComp); HInsert(&heap, 'A'); HInsert(&heap, 'B'); HInsert(&heap, 'C'); printf("%c \n", HDelete(&heap)); HInsert(&heap, 'A'); HInsert(&heap, 'B'); HInsert(&heap, 'C'); printf("%c \n", HDelete(&heap)); while (!HIsEmpty(&heap)) printf("%c \n", HDelete(&heap)); return 0; } |
DataPriorityComp 는 첫 번째 인자로 전달된 문자의 아스키 코드 값이 작을 때 0보다 큰 값을 반환하도록 정의되었습니다. 이 함수를 정의하는 기준을 앞서 다음과 같이 결정하였습니다. 첫 번째 인자의 우선순위가 높다면, 0보다 큰 값이 반환되도록 정의합니다. 두 번째 인자의 우선순위가 높다면, 0보다 작은 값이 반환되도록 정의합니다. 첫 번째, 두 번째 인자의 우선순위가 동일하다면, 0이 반환되도록 정의합니다. 아스키 코드 값이 작은 문자의 우선순위가 더 높다.
힙을 이용한 우선순위 큐의 구현
힙을 완성하였으니 이를 기반으로 우선순위 큐를 구현할 차례입니다.
우선순위 큐 자료구조의 ADT
우선순위 큐의 초기화를 진행합니다. 우선수위 큐 생성후 제일 먼저 호출되어야 하는 함수입니다. 우선순위 큐가 빈 경우 참을, 그렇지 않은 경우 거짓을 반환합니다. 우선순위 큐에 데이터를 저장합니다. 매개변수 data로 전달된 값을 저장합니다. 우선순위가 가장 높은 데이터를 삭제합니다. 삭제된 데이터는 반환합니다. 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 합니다.
#include <stdio.h> #include "PriorityQueue.h" int DataPriorityComp(char ch1, char ch2) { return ch2 - ch1; } int main(void) { PQueue pq; PQueueInit(&pq, DataPriorityComp); PEnqueue(&pq, 'A'); PEnqueue(&pq, 'B'); PEnqueue(&pq, 'C'); printf("%c \n", PDequeue(&pq)); PEnqueue(&pq, 'A'); PEnqueue(&pq, 'B'); PEnqueue(&pq, 'C'); printf("%c \n", PDequeue(&pq)); while (!PQIsEmpty(&pq)) printf("%c \n", PDequeue(&pq)); return 0; } |