우선순위 큐

 

 

우선순위 큐의 구현 방법

 

우선순위 큐를 구현하는 방법은 다음과 같이 세 가지로 구분할 수 있다.

 

• 배열 기반 구현
• 연결 리스트 기반 구현
• 힙을 이용하는 방법

 

배열이나 연결 리스트를 이용하면 우선순위 큐를 매우 간단히 구현할 수 있다.

참고로 다음 그림에서, 저장된 숫자는 데이터인 동시에 우선순위 정보라고 가정하였다.

숫자 1이 가장 높은 우선순위를 뜻하며, 이보다 값이 커질수록 우선순위는 낮아진다고 가정하였다.

 

 

배열의 경우, 데이터의 우선순위가 높을수록 배열의 앞쪽에 데이터를 위치시킨다.

이렇게 하면 우선순위가 높은 데이터를 반환 및 소멸하는 것이 어려운 일이 아니다.

하지만 다음과 같은 단점이 따른다.

 

데이터를 삽입 및 삭제하는 과정에서

데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반해야한다.

 

이는 배열의 대표적인 단점이다. 하지만 이보다 더 큰 문제는 다음과 같다.

 

삽입의 위치를 찾기 위해서

배열에 저장된 모든 데이터와 우선순위의 비교를 진행해야 할 수도 있다.

 

이는 데이터의 수가 적은 경우 큰 단점이 되지 않을 수 있다.

하지만 데이터의 수가 많아지면,

그래서 연결된 노드의 수가 많아지면,

노드의 수에 비례해서 성능을 저하시키는 주원이이 된다.

그래서 우선순위 큐는

단순 배열도 연결 리스트도 아닌 '힙'이라는 자료구조를 이용해서 구현하는 것이 일반적이다.

 

 

힙의 소개

 

힙은 '이진 트리'이되 '완전 이진 트리'이다.

그리고 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 크거나 같아야 한다.

즉 루트 노드에 저장된 값이 가장 커야 한다.

 

위에서 말하는 값은 말 그대로 "값" 자체가 될 수도 있고,

우선순위 큐에서 말하는 "우선순위"가 될 수도 있다.

그런데 우리는 힙을 기반으로 우선순위 큐를 구현할 계획을 갖고 있으니,

위 문장의 "값"은 "우선순위"가 된다.

 

그럼 위 문장에서 말하는 형태의 이진 트리를 그림으로 그려 보이겠다.

 

아래와 같이 노드로 올라갈수록

저장된 값이 커지는 완전 이진 트리를 가리켜 최대 힙이라 한다.

 

 

반면 다음 그림과 같이 루트 노트로 올라갈수록 저장된 값이

작아지는 완전 이지느 트리를 가리켜 최소 힙이라 한다.

 

 

이렇듯 힙은 루트 노드에 우선순위가 가장 높은 데이터를 위치시킬 수 있는 자료구조이니,

이를 기반으로 하면 우선순위 큐를 간단히 구현할 수 있지 않겠는가!

참고로 위의 두 그림에서 보이듯이, 힙은 무엇인가를 쌓아 놓는 더미와 흡사하다 하여 지어진 이름이다.

영단어 heap은 '무엇인가를 차곡차곡 쌓아 올린 더미'라는 뜻을 지닌다.

 

 

힙의 구현과 우선순위 큐의 완성

 

 

힙의 구현은 곧 우선순위 큐의 완성으로 이어진다.

따라서 힙과 우선순위 큐를 동일하게 인식하는 경향이 매우 강하다.

하지만 이는 정확하지 않은 것이니,

우선순위 큐와 힙을 어느 정도는 구분할 수 있으면 좋다.

힙은 우선순위 큐의 구현에 딱 어울리는, 완전 이진 트리의 일종이라는 사실을 기억하기 바란다.

 

힙을 구현하고 이를 기반으로 우선순위 큐를 구현하고자 한다.

그런데 힙의 구현을 위해서는 데이터의 저장과 삭제의 방법을 먼저 알아야 한다.

따라서 먼저 데이터의 저장과정을 '최소 힙'을 기준으로 설명하고자 한다.

 

위 그림에 쓰여있는 숫자를 데이터 겸 우선순위라 하자,

그리고 숫자가 작을수록 우선순위가 높다고 가정하자.

그렇다면 위 그림은 우선순위 관점에서 힙이 맞다.

완전 이진 트리이면서, 어느 위치에서 다음 식이 성립하기 때문이다.

 

자식 노드 데이터의 우선 순위  <= 부모 노드 데이터의 우선 순위

 

힙에서 삽입은 가장 마지막 위치에 삽입할 노드를 생성하고

계속해서 부모 노드와 우선 순위를 비교하여 제자리를 찾아가게 한다.

 

삭제 과정은 마지막 노드를 루트 노드 자리에 옮긴 다음에,

계속해서 자식 노드와의 비교를 통해서 제자리를 찾아가게 한다.

 

 

삽입 삭제 과정에서 보인 성능 평가

 

힙에 대한 이론적인 설명이 일단락되었으니 다음 질문에 답을 해보자.

 

우선순위 큐의 구현에 있어서

단순 배열이나 연결 리스트보다 힙이 더 적합한 이유는 어디에 있는가?

 

데이터 저장과 삭제에 대한 시간 복잡도에 있다.

 

• 배열 기반 데이터 저장의 시간 복잡도             O(n)
• 배열 기반 데이터 삭제의 시간 복잡도             O(n)

 

• 연결 리스트 기반 데이터 저장의 시간 복잡도             O(n)
• 연결 리스트 기반 데이터 삭제의 시간 복잡도             O(1)

 

 

• 힙 기반 데이터 저장의 시간 복잡도             O(log₂n)
• 힙 기반 데이터 삭제의 시간 복잡도             O(log₂n)

 

힙은 완전 이진 트리이므로,

힙에 저장할 수 있는 데이터의 수는 트리의 높이가 하나 늘 때 마다

두 배씩 증가한다.

떄문에 데이터의 수가 두 배 늘 떄마다, 비교연산의 횟수는 1회 증가한다.

바로 이 사실을 근거로 위의 결론을 내릴 수 있다.

 

이로써 우선순위 큐의 구현에 있어

배열보다도 연결 리스트보다도 힙이 어울리는 이유를

객관적으로 정리하였다.

 

 

그렇다면 힙의 구현에 어울리는 것은 연결 리스트일까? 배열일까?

 

힙은 배열 기반으로 구현해야 한다.

실제로 힙의 구현은 배열을 기반으로 구현하는 것이 윈치그올 여겨지고 있는데,

그 이유는 다음과 같다.

 

연결 리스트를 기반으로 힙을 구현하면,

새로운 노드를 힙의 '마지막 위치'에 추가하는 것이 쉽지 않다.

 

사소한 이유 같고, 그래서 연결 리스트를 기반으로 쉽게 해결 가능한 문제처럼 보이지만,

이는 결코 간단한 문제가 아니다.

하지만 배열 기반의 힙이라면 이는 매우 간단한 문제가 된다.

그래서 힙과 같이, 새로운 노드를 추가한 이후에도 완전 이진 트리를 유지해야 하는 경우에는

연결 리스트가 아닌 배열을 기반으로 트리를 구현해야 한다.

 

왼쪽, 오른쪽 자식 노드이 인덱스 값을 얻는 방법,

부모 노드의 인덱스 값을 얻는 방법

 

• 왼쪽 자식 노드의 인덱스 값　　　　　부모 노드의 인덱스 값 x 2

• 오른쪽 자식 노드의 인덱스 값　　　　부모 노드의 인덱스 값 x 2 + 1

• 부모 노드의 인덱스 값　　 　　　　　부모 노드의 인덱스 값 / 2

 

해당 계산 값이 맞으려면

구현의 편의를 위해서

인덱스가 0인 위치의 배열 요소는 사용하지 않는 다는 것을 기억하자.

 

// SimpleHeap.h

#ifndef __SIMPLE_HEAP_H__
#define __SIMPLE_HEAP_H__

#define TRUE		1
#define FALSE		0

#define HEAP_LEN	100

typedef char HData;
typedef int Priority;

typedef struct _heapElem
{
	Priority pr;	// 값이 작으로수록 높은 우선순위
	HData data;
} HeapElem;

typedef struct _heap
{
	int numOfData;
	HeapElem heapArr[HEAP_LEN];
} Heap;

void HeapInit(Heap* ph);
int HIsEmpty(Heap* ph);

void HInsert(Heap* ph, HData data, Priority pr);
HData HDelete(Heap* ph);

#endif

 

// SimpleHeap.c
#include "SimpleHeap.h"

void HeapInit(Heap* ph) // 힙의 초기화
{
    ph->numOfData = 0;
}

int HIsEmpty(Heap* ph)
{
    if (ph->numOfData == 0)
        return TRUE;
    else
        return FALSE;
}

int GetParentIDX(int idx)
{
    return idx / 2;
}

int GetLChildIDX(int idx)
{
    return idx * 2;
}

int GetRChildIDX(int idx)
{
    return GetLChildIDX(idx) + 1;
}

// 두 개의 자식 노드 중 높은 우선순위의 자식 노드 인덱스 값 반환
int GetHiPriChildIDX(Heap* ph, int idx)
{
    if (GetLChildIDX(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);

    }
}

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;
}

HData HDelete(Heap* ph)
{
    HData retData = (ph->heapArr[1]).data;  // 삭제할 데이터 임시 저장
    HeapElem lastElem = ph->heapArr[ph->numOfData];

    int parentIdx = 1;  // 루트 노드의 Index
    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;
}

 

 

 

해당 게시물은 윤성우의 열혈 자료구조를 기반으로 제작되었습니다.