Data Structure & Algorithm/Data Structure
[Data Structure] Chapter 09: 우선순위 큐(Priority Queue)와 힙(Heap)
시데브
2023. 9. 1. 16:45
자료구조 큐에 우선순위를 적용한 우선순위 큐를 이해하고,
힙을 이용해 우선순위 큐를 구현해보자.
우선순위 큐
- 우선순위 큐(Priority Queue): 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나오는 규칙이 적용된 큐를 의미한다.
우선순위 큐의 구현 방법
- 배열 기반으로 구현하는 방법
- 연결 리스트를 기반으로 구현하는 방법
- 힙(heap)을 이용하는 방법
>> 배열과 연결리스트를 기반으로 하는 방법은 우선순위를 비교할 때, 모든 노드를 대상으로 비교를 진행하기 때문에, 노드의 수가 많아질수록 성능이 저하된다. 따라서, 일반적으로 우선순위 큐는 힙을 이용하여 구현한다.
힙
- 힙(heap): 완전 이진 트리의 일종으로, 우선순위 큐의 구현을 위해 만들어진 자료구조이다.
- 자식 노드와 부모 노드의 관계가 우선순위에 따라 정렬되어있는 완전 이진 트리이다.
힙의 구현
파일명: 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
Step by step goes a long way.
gmlwjd9405.github.io
728x90
반응형