[Data Structure] Chapter 09: 우선순위 큐(Priority Queue)와 힙(Heap)

자료구조 큐에 우선순위를 적용한 우선순위 큐를 이해하고,
힙을 이용해 우선순위 큐를 구현해보자.

 

 

우선순위 큐

• 우선순위 큐(Priority Queue): 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 규칙이 적용된 큐를 의미한다.

 

우선순위 큐의 구현 방법

• 배열 기반으로 구현하는 방법
• 연결 리스트를 기반으로 구현하는 방법
• 힙(heap)을 이용하는 방법

 

>> 배열과 연결리스트를 기반으로 하는 방법은 우선순위를 비교할 때, 모든 노드를 대상으로 비교를 진행하기 때문에, 노드의 수가 많아질수록 성능이 저하된다. 따라서, 일반적으로 우선순위 큐는 힙을 이용하여 구현한다.

 

 

힙

• 힙(heap): 완전 이진 트리의 일종으로, 우선순위 큐의 구현을 위해 만들어진 자료구조이다.
• 자식 노드와 부모 노드의 관계가 우선순위에 따라 정렬되어있는 완전 이진 트리이다.

 

좌측부터 최대 힙(max heap), 최소 힙(min heap)

 

 

힙의 구현

 

HInsert와 HDelete

 

 파일명: 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;
}

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

void HInsert(Heap * ph, HData data, Priority pr)
{
    int idx = ph->numOfData+1;
    HeapElem nelem = {pr, data};

    while(idx != 1)
    {
        if(ph->heapArr[GetParentIDX(idx)].pr>pr)
        {
            ph->heapArr[idx]=ph->heapArr[GetParentIDX(idx)];
            idx = GetParentIDX(idx);
        }
        else
            break;
        
    }
}

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) //자식노드보다 우선순위가 높으면 stop!
            break;
        ph->heapArr[parentIdx]=ph->heapArr[childIdx];
        parentIdx=childIdx;
    }

    ph->heapArr[parentIdx]=lastElem;
    ph->numOfData -= 1;
    return retData;
}

 

 파일명: SimpleHeapMain.c

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

A 
A 
B 
B 
C 
C

 

>> 위에서 구현된 Heap에서는 사용자가 일일이 우선순위를 넣어줘야 한다는 단점이 있다. 그렇다면, 이번에는 데이터 자체에서 우선순위를 판단하도록 구현해보자.

 

 

 파일명: UsefulHeap.h

#ifndef __USEFUL_HEAP_H__
#define __USEFUL_HEAP_H__

#define TRUE        1
#define FALSE       0

#define HEAP_LEN    100

typedef char HData;  
typedef int PriorityComp(HData d1, HData d2);   //책에는 typedef int (*PriorityComp)(HData d1, HData d2);로 돼있는데, 그렇게 하면 아래 선언할 때 이중포인터 선언이 돼버림 

typedef struct _heap
{
    PriorityComp * comp;  
    int numOfData;
    HData heapArr[HEAP_LEN];
} Heap;

void HeapInit(Heap * ph, PriorityComp pc);
int HIsEmpty(Heap * ph);

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

#endif

 

 파일명: UsefulHeap.c

#include "UsefulHeap.h"

void HeapInit(Heap * ph, PriorityComp pc)
{
    ph->numOfData = 0;
    ph->comp = pc;
}

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->comp(ph->heapArr[GetLChildIDX(idx)], ph->heapArr[GetRChildIDX(idx)]) < 0)
            return GetRChildIDX(idx);
        else
            return GetLChildIDX(idx);
    }
}

void HInsert(Heap * ph, HData data)
{
    int idx = ph->numOfData+1;

    while(idx != 1)
    {
        if(ph->comp(data, ph->heapArr[GetParentIDX(idx)]) > 0)
        {
            ph->heapArr[idx] = ph->heapArr[GetParentIDX(idx)];
            idx = GetParentIDX(idx);
        }
        else
            break;
    }

    ph->heapArr[idx] = data;
    ph->numOfData +=1;
}

HData HDelete(Heap * ph)
{
    HData retData = ph->heapArr[1];
    HData lastData = ph->heapArr[ph->numOfData];

    int parentIdx = 1;
    int childIdx;

    while(childIdx = GetHiPriChildIDX(ph, parentIdx))
    {
        if(ph->comp(lastData, ph->heapArr[childIdx]) >= 0) 
            break;
        ph->heapArr[parentIdx] = ph->heapArr[childIdx];
        parentIdx = childIdx;
    }

    ph->heapArr[parentIdx] = lastData;
    ph->numOfData -= 1;
    return retData;
}

 

 파일명: UsefulHeapMain.c

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

A 
A 
B 
B 
C 
C

 

 

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

 

배열 기반 우선순위 큐

• 데이터 저장의 시간 복잡도: 모든 노드와 하나하나 우선순위를 비교하고 데이터를 삽입하므로, $O(n)$
• 데이터 삭제의 시간 복잡도: 맨 앞의 노드를 삭제하기만 하면 되기 때문에, $O(1)$

 

연결 리스트 기반 우선순위 큐

• 데이터 저장의 시간 복잡도: 모든 노드와 하나하나 우선순위를 비교하고 데이터를 삽입하므로, $O(n)$
• 데이터 삭제의 시간 복잡도: 맨 앞의 노드를 삭제하기만 하면 되기 때문에, $O(1)$

 

힙 기반 우선순위 큐

• 데이터 저장의 시간 복잡도: 트리의 높이에 해당하는 수만큼만 비교연산을 진행하면 되기 때문에, $O(log_2n)$
• 데이터 삭제의 시간 복잡도: 트리의 높이에 해당하는 수만큼만 비교연산을 진행하면 되기 때문에, $O(log_2n)$

>> 데이터의 수가 2배씩 증가해도 연산 횟수는 1씩만 늘어나기 때문에 $log_2$로 표현할 수 있다.

 

 

힙을 기반으로 우선순위 큐 구현

 

우선순위 큐의 ADT

void * PQueueInit(PQueue * ppq, PriorityComp pc);
- 우선순위 큐의 초기화를 진행한다.
- 우선순위 큐 생성 후 제일 먼저 호출되어야 하는 함수이다.

void * PQIsEmpty(PQueue * ppq);
- 우선순위 큐가 빈 경우 TRUE(1), 그렇지 않은 경우 FALSE(0)을 반환한다.

void * PEnqueue(PQueue * ppq, PQData data);
- 우선순위 큐에 데이터를 저장한다. 매개변수 data로 전달된 값을 저장한다.

void * PDequeue(PQueue * ppq);
- 우선순위가 가장 높은 데이터를 삭제한다.
- 삭제된 데이터는 반환된다.
- 본 함수의 호출을 위해서는 데이터가 하나 이상 존재함이 보장되어야 한다.

 

 파일명: PriorityQueue.h

#ifndef __PRIORITY_QUEUE_H__
#define __PRIORITY_QUEUE_H__

#include "UsefulHeap.h"

typedef Heap PQueue;
typedef HData PQData;

void PQueueInit(PQueue * ppq, PriorityComp pc);
int PQIsEmpty(PQueue * ppq);

void PEnqueue(PQueue * ppq, PQData data);
PQData PDequeue(PQueue * ppq);

#endif

 

 파일명: PriorityQueue.c

#include "PriorityQueue.h"
#include "UsefulHeap.h"

void PQueueInit(PQueue * ppq, PriorityComp pc)
{
	HeapInit(ppq, pc);
}

int PQIsEmpty(PQueue * ppq)
{
	return HIsEmpty(ppq);
}

void PEnqueue(PQueue * ppq, PQData data)
{
	HInsert(ppq, data);
}

PQData PDequeue(PQueue * ppq)
{
	return HDelete(ppq);
}

 

 파일명: PriorityQueueMain.c

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

A 
A 
B 
B 
C 
C

 

 

+문제 09-1

heap 헤더 파일의 HData 선언을 문자열로 바꿔주고,

 

typedef char HData -> typedef char * HData;

 

main 파일만 다음과 같이 변경해주면 된다.

 

#include <stdio.h>
#include <string.h>
#include "PriorityQueue.h"

int DataPriorityComp(char * ch1, char * ch2)
{
	return strlen(ch2)-strlen(ch1);
}

int main(void)
{
	PQueue pq;
	PQueueInit(&pq, DataPriorityComp);

	PEnqueue(&pq, "Good Morning");
	PEnqueue(&pq, "I am a boy");
	PEnqueue(&pq, "Priority Queue");
	PEnqueue(&pq, "Do you like coffee");
	PEnqueue(&pq, "I am so happy");


	while(!PQIsEmpty(&pq))
		printf("%s \n", PDequeue(&pq));

	return 0;
}

I am a boy 
Good Morning 
I am so happy 
Priority Queue 
Do you like coffee

---

참고자료

• 윤성우, <윤성우의 열혈 자료구조>, 오렌지미디어, 2022.04.11
• https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html

[자료구조] 힙(heap)이란 - Heee's Development Blog