문제 09 -1 우선순위 큐의 활용
// UsefulHeap.h
#pragma once
#define TRUE 1
#define FALSE 0
#define HEAP_LEN 100
// typedef char HData;
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);
//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)
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;
}
//PriorityQueue.h
#pragma once
#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);
//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);
}
// Main. c
#include <stdio.h>
#include <string.h>
#include "PriorityQueue.h"
int DatapriorityComp(char * str1, char * str2)
{
return strlen(str2) - strlen(str1);
}
int main()
{
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;
}
