우선순위 큐

우선순위 큐는 이름에서도 의미하듯 우선순위를 정한 큐이다. 큐의 경우에는 줄서기에 비유한다면 우선순위 큐는 응급실의 응급 상황인 사람이 먼저 들어가는 상황에 비유해보자. 이처럼 우선순위가 부여가 된다. 

앞서 배운 큐의 핵심 연산은 2가지이다. 
enqueue() 데이터 삽입
dequeue() 데이터 삭제
이와 마찬가지로 우선순위 큐의 핵심 연산도 2가지 모두 동일하다.
반면에 연산의 결과는 차이가 있다. 큐의 경우에는 먼저 들어간 데이터가 먼저 나오지만 우선순위 큐는 우선순위가 더 높은 데이터가 먼저 나온다.

우선순위 큐를 구현하기 위해서 아래와 같은 3가지의 방법이 있다.
・배열 기반 구현
・연결 리스트 기반 구현
・힙 기반 구현

우선 배열과 연결 리스트를 이용하면 간단하게 구현할 수 있다. 
1) 배열의 경우, 우선순위가 높은 데이터를 배열의 앞쪽에 위치 시킨다. 하지만 이렇게 하면 생성과 소멸은 문제가 되지않지만 데이터를 삽입하는 과정에서 모든 데이터와 우선순위를 비교해야하는 단점이 따른다.

2) 연결 리스트의 경우, 배열과 마찬가지로 삽입되는 위치를 찾기위해 첫 번째 노드부터 마지막 노드까지 순회를 해야하는 단점이 따른다. 데이터 수가 적으면 문제가 되지않지만 데이터가 많다면 성능을 저하시키는 원인이 된다. 그래서 우선순위 큐는 힙이라는 자료 구조를 이용해 구현하는 방법이 일반적이다.

힙이라는 것은 이진 트리이자, 완전 이진 트리이다. 그리고 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다. 즉, 루트 노드의 값이 가장 커야한다.
위에서 말한 값은 '데이터'가 될수도 있고 '우선순위'가 될수도 있다. 그런데 우리는 힙을 이용하여 우선순위 큐를 구현할 것이기 때문에 위의 값은 '우선순위'가 된다.

최대힙

위 그림과 같이 루트 노드로 올라갈수록 값이 커지는 힙을 최대힙이라고 한다.

최소힙

위 그림과 같이 루트 노드로 올라갈수록 값이 작아지는 힙을 최소힙이라고 한다.

1) 힙 데이터 저장 과정
위 그림과 같은 최소힙을 기준으로 설명하겠다. 위의 값을 우선순위라고 정하고 숫자가 작을수록 우선순위가 높다고 가정하자. 그렇다면 위의 가정에서는 힙이 맞다. 완전 이진 트리이며 어느 위치에서든 자식 노드보다 부모 노드가 우선순위가 크기 때문이다.

위 그림에서 2를 저장한다고 가정해보자. 저장한 이후에도 힙의 조건을 맞추는게 여간 쉬운일이 아니다. 따라서 필자가 먼저 제시를 하자면 새로 추가되는 데이터는 우선순위가 가장낮다는 가정하에 마지막 위치에 저장한다. 그리고는 부모 노드와 우선순위를 비교해서 위치가 바뀌어야 한다면 바꿔준다. 바뀐 다음에도 제대로된 위치를 찾기 전까지 계속해서 부모 노드와 비교를 한다. 말이 어렵지만 다음 그림을 보면 이해할 수 있을 것이다.

1. 먼저 2라는 데이터를 우선순위가 가장 낮은 위치에 저장

2라는 데이터가 추가된 모습

2. 추가된 데이터와 부모 노드를 우선순위 비교하며 바꿔준다. 12와 2는 우선순위가 2가 더 높으니 바꿔준다.

2와 12를 바꿔준 모습

3. 다시 부모 노드와 우선순위를 비교

2와 3을 비교중인 상태

4. 우선순위가 2가 3보다 크니까 다시 바꿔준다.

2와 3을 바꿔준 모습

5. 2와 1을 마지막으로 비교한다. 하지만 1이 우선순위가 더 높기 때문에 바꿔주지 않으며 저장된 위치를 찾으며 저장은 종료가 된다.

2와 1을 비교 후 제대로된 자리를 찾은 모습

2) 힙 데이터 삭제 과정
힙의 삭제는 당연히 가장 우선순위가 높은 루트 노드가 삭제될 것이다. 루트 노드를 삭제하는 것은 어렵지 않지만 삭제 후에도 힙의 구조를 유지하는데에 있어서 고민이 된다. 하지만 삽입에서의 방법을 동일하게 처리하면 그렇게 어렵지 않다. 먼저 마지막 노드(12)를 루트 노드(1)에 삽입을 하며 원래의 위치를 찾게하면 완성이 된다. 글로 잘 이해가 안된다면 아래의 그림을 보자.

1. 마지막 노드를 루트 노드로 이동하는 모습

마지막 노드를 루트 노드로 이동

2. 12데이터를 원래의 자리로 찾기 위해 두 개의 자식 중 우선순위가 높은 것과 비교한다. 위 그림에서는 2가 우선순위가 높기 때문에 2와 자리를 교환한다.

12와 자식 노드 중 우선순위 값이 더 큰 2와 비교

3. 이번에도 전의 단계와 동일하게 두 개의 자식 중 우선순위가 높은 것과 비교하며 교환한다. 이번에는 3이 되겠다.

12와 3을 위치를 교환한 모습

4. 마지막으로 자식 노드인 70과 비교를 하지만 우선순위가 12가 더 큰 관계로 삭제가 종료가 된다.

우선순위 큐는 힙으로 구현하는 것이 효율이 좋다고 판단했으니 힙을 연결리스트 또는 배열로 구현해야하는데 어떤 것이 더 효율적일까? 연결리스트로 구현을 한다면 새로운 노드를 마지막 위치에 추가하는 것이 쉽지가 않다. 그렇기 때문에 배열을 기반으로 구현하는 것이 효율적이다.

배열을 이용한 트리

구현의 편의를 위해 0번째 인덱스 값은 사용하지 않는다. 삽입과 삭제를 위해 자식 노드 및 부모 노드의 위치를 알아야하는데 이는 아래의 공식에서 인덱스를 얻어올 수 있다.

・왼쪽 자식의 노드의 인덱스 값 : 부모 노드의 인덱스 값 × 2
・오른쪽 자식의 노드의 인덱스 값 : 부모 노드의 인덱스 값 × 2 + 1
・부모 노드의 인덱스 값 : 자식 노드의 인덱스 값 ÷ 2

의외로 간단하다. 이진 트리는 레벨이 증가함에 따라 추가할 수 있는 자식 노드의 수가 두 배씩 증가하는 구조이다 보니 2를 나누고 곱하여서 부모 노드와 자식 노드의 인덱스 값을 얻어올 수 있다. 한 가지 주의할 점은 부모 노드의 인덱스를 구할 때 실수형이 아닌 정수형으로 계산되어야한다는 점이다.

원리를 이해했으니 구현해보자. 구현과정에서 눈여겨볼 과정은 데이터의 삭제 과정이다. 위의 개념으로는 마지막 노드를 루트 노드에 삽입하여 자식 노드와 비교하여 제대로된 위치까지 계속해서 값을 변경해나갔지만 코드적으로 일일이 위치 변경을 하면 연산이 많이 들기 때문에 최종 목적지를 찾아서 단번에 바꿔주도록 구현하였다. 이해가 안된다면 그림을 그려가면서 코드를 디버깅해보자.

#include <iostream>
 
using namespace std;
 
#define MAX_LENGTH 100
 
// 힙 노드 구조체
typedef struct heapNode
{
    int priority;    // 값이 작을수록 우선순위가 높음
    int data;        // 데이터
}HEAPNODE;
 
// 힙 구조체
typedef struct heap
{
    heap() : numOfData(0) { memset(dataArr, 0, sizeof(dataArr)); }
 
    int numOfData;
    HEAPNODE dataArr[MAX_LENGTH];
}HEAP;
 
// 힙이 비어있는지 검사하는 함수
bool IsEmpty(HEAP* heap)
{
    if (heap->numOfData == 0)
        return true;
 
    return false;
}
 
// 부모 노드의 인덱스 값 얻기
int GetParentIndex(int index)
{
    return index / 2;
}
 
// 왼쪽 자식 노드 인덱스 값 얻기
int GetLeftChildIndex(int index)
{
    return index * 2;
}
 
// 오른쪽 자식 노드 인덱스 값 얻기
int GetRightChildIndex(int index)
{
    return index * 2 + 1;
}
 
// 두 개의 자식 중 우선순위가 높은 자식의 인덱스 값 얻기
int GetHighPriorityIndex(HEAP* heap, int index)
{
    // 자식 노드가 없을 경우
    if (GetLeftChildIndex(index) > heap->numOfData)
    {
        // 0을 반환
        return 0;
    }
    // 자식 노드가 하나인 경우
    else if (GetLeftChildIndex(index) == heap->numOfData)
    {
        // 왼쪽 노드의 인덱스를 반환
        return GetLeftChildIndex(index);
    }
    // 자식 노드가 두개인 경우
    else
    {
        // 왼쪽 자식과 오른쪽 자식의 우선순위를 비교후 인덱스 반환 (작은 값이 우선순위가 더 높음)
        if (heap->dataArr[GetLeftChildIndex(index)].priority > heap->dataArr[GetRightChildIndex(index)].priority)
            return GetRightChildIndex(index);
        else
            return GetLeftChildIndex(index);
    }
}
 
// 힙의 데이터 저장
void HeapInsert(HEAP* heap, int data, int priority)
{
    int index = heap->numOfData + 1;
    HEAPNODE node = { priority, data };
 
    // 루트 노드가 아닐경우
    while (index != 1)
    {
        if (priority < heap->dataArr[GetParentIndex(index)].priority)
        {
            heap->dataArr[index] = heap->dataArr[GetParentIndex(index)];
            index = GetParentIndex(index);
        }
        else
        {
            break;
        }
    }
 
    // 인덱스의 위치에 맞게 노드를 삽입 및 데이터 개수 하나 증가
    heap->dataArr[index] = node;
    heap->numOfData += 1;
}
 
// 힙의 데이터 삭제
int HeapDelete(HEAP* heap)
{
    // 반환을 위한 삭제할 데이터를 저장
    int deleteData = heap->dataArr[1].data;
    
    // 마지막 위치에 있는 노드를 저장
    HEAPNODE lastNode = heap->dataArr[heap->numOfData];
    
    // parentIndex에는 마지막 노드가 저장될 위치정보가 담김
    int parentIndex = 1;
    int childIndex = 0;
 
    // 루트 노드의 우선순위가 높은 자식 노드로 반복문 시작
    while (childIndex = GetHighPriorityIndex(heap, parentIndex))
    {
        // 마지막 노드의 우선순위가 높으면 반복문 탈출
        if (lastNode.priority <= heap->dataArr[childIndex].priority)
            break;
 
        // 마지막 노드보다 우선순위가 높으니 비교대상 노드의 위치를 한 레벨 올림 (실제로 올림)
        heap->dataArr[parentIndex] = heap->dataArr[childIndex];
 
        // 마지막 노드가 저장될 위치정보를 한 레벨 내림 (인덱스 값만 저장하고 실제로 올리지 않으며 반복문 탈출 시 129Line에서 저장)
        parentIndex = childIndex;
    }
 
    // 마지막 노드 최종 저장
    heap->dataArr[parentIndex] = lastNode;
    heap->numOfData -= 1;
    
    return deleteData;
}
 
int main()
{
    HEAP heap = {};
 
    HeapInsert(&heap, 'A', 1);
    HeapInsert(&heap, 'B', 2);
    HeapInsert(&heap, 'C', 3);
    HeapInsert(&heap, 'D', 4);
    HeapInsert(&heap, 'E', 5);
    HeapInsert(&heap, 'F', 6);
    HeapInsert(&heap, 'G', 7);
    printf("%c \n", HeapDelete(&heap));
    printf("======================== \n");
 
    HeapInsert(&heap, 'A', 1);
    HeapInsert(&heap, 'B', 2);
    HeapInsert(&heap, 'C', 3);
    printf("%c \n", HeapDelete(&heap));
    printf("======================== \n");
 
    while (IsEmpty(&heap) == false)
    {
        printf("%c \n", HeapDelete(&heap));
    }
}