.png)
.png)
우선순위 큐
큐는 먼저 들어간 데이터가 먼저 나오나, 우선순위 큐는 들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다.
응급실로 비유하면 촌각을 다투며, 생명이 위급한 환자 또는 내일까지 기다리기에는 무리인 환자가 해당됨.
우선순위 정보는 거의 정수로 표현되나, 꼭 정수만 사용되지는 않음, 정수로 표현할 때는 꼭 정수의 값이 클수록 우선순위가 높지 않음.
우선순위는 같을 수 있음.
우선순위 구현 방식
배열, 연결리스트, 힙(Heap)이 존재.
배열을 이용한 우선순위 큐는 구현은 쉬우나, 데이터를 삽입 및 삭제하는 과정에서 데이터를 한 칸씩 뒤로 밀거나 한 칸씩 앞으로 당기는 연산을 수반하기 때문에 비효율적이다. 그리고 삽입의 위치를 찾기위해 배열에 저장된 모든 데이터와 우선순위 비교를 진행해야 할 수 있다.
두 번째의 단점은 연결 리스트에서도 있음.
때문에 우선순위 큐는 대부분 힙으로 구현한다.
힙이란?
무엇인가를 차곡차곡 쌓아올린 더미를 뜻하는 영단어.
이진 트리이되 완전 이진 트리에 해당, 모든 노드에 저장된 값은 자식 노드에 저장된 값보다 더 크거나 같아야 한다.(루트 노드의 값이 가장 크다.)
위에서 말하는 값은 말 그대로 값이 될 수도 있고, 우선순위가 될 수도 있다.
루트 노드로 올라갈수록 값이 커지면 최대 힙(max heap), 작아지면 최소 힙(mix 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 _heapEleam
{
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 * phm 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 GetLhildIDX(idx)+1;
}
int GetHiPrihildIDX(Heap * ph, int idx)
{
if(GetLChildIDX(idx) > ph->numOfData)
return 0;
else if(GetLChildIdx(idx == ph->numOfData))
return GetLhildIDX(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 != i)
{
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;
int childIdx;
while(childIdx = GetHiPrihildIDX(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;
}// 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
더 효율적인 힙 소스코드
// 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 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->heapArr[GetLChildIDX(idx)].pr > ph->heapArr[GetRChildIDX(idx)].pr)
// return GetRChildIDX(idx);
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 (pr < (ph->heapArr[GetParentIDX(idx)].pr))
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 lastElem = ph->heapArr[ph->numOfData];
int parentIdx = 1;
int childIdx;
while (childIdx = GetHiPriChildIDX(ph, parentIdx))
{
// if (lastElem.pr <= ph->heapArr[childIdx].pr)
if (ph->comp(lastElem, ph->heapArr[childIdx]) >= 0)
break;
ph->heapArr[parentIdx] = ph->heapArr[childIdx];
parentIdx = childIdx;
}
ph->heapArr[parentIdx] = lastElem;
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));
}A A B B C C
위 코드를 기반으로 한 우선순위 큐 구현
// 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
댓글 없음:
댓글 쓰기