728x90
반응형
#include <stdio.h>
#define TRUE 1
#define FALSE 0
#define HEAP_LEN 100
typedef struct _heapElem
{
int pr;
char data;
}HeapElem;
typedef struct _heap
{
int numOfData;
HeapElem heapArr[HEAP_LEN];
}Heap;
void HeapInit(Heap* copy)
{
copy->numOfData = 0;
}
int GetParentIDX(int idx)
{
return idx / 2;
}
void Insert(Heap* copy, char data, int pr)
{
int idx = copy->numOfData + 1;
HeapElem elem = { data, pr };
while (idx != 1)
{
if (pr < (copy->heapArr[GetParentIDX(idx)].pr))
{
copy->heapArr[idx] = copy->heapArr[GetParentIDX(idx)];
idx = GetParentIDX(idx);
}
else
break;
}
copy->heapArr[idx] = elem;
copy->numOfData += 1;
}
int GetLchildIDX(int idx)
{
return idx * 2;
}
int GetRchildIDX(int idx)
{
return GetLchildIDX(idx) + 1;
}
int GetHiPriChildIDX(Heap* copy, int idx)
{
if (GetLchildIDX(idx) > copy->numOfData)
return 0;
else if (GetLchildIDX(idx) == copy->numOfData)
return GetLchildIDX(idx);
else
{
if (copy->heapArr[GetLchildIDX(idx)].pr
> copy->heapArr[GetRchildIDX(idx)].pr)
return GetRchildIDX(idx);
else
return GetLchildIDX(idx);
}
}
char Delete(Heap* copy)
{
char retData = (copy->heapArr[1]).data;
HeapElem lastElem = copy->heapArr[copy->numOfData];
int parentIdx = 1;
int childIdx;
while (childIdx = GetHiPriChildIDX(copy, parentIdx))
{
if (lastElem.pr <= copy->heapArr[childIdx].pr)
break;
copy->heapArr[parentIdx] = copy->heapArr[childIdx];
parentIdx = childIdx;
}
copy->heapArr[parentIdx] = lastElem;
copy->numOfData -= 1;
return retData;
}
int Empty(Heap* copy)
{
if (copy->numOfData == 0)
return TRUE;
else
return FALSE;
}
int main(void)
{
Heap heap;
HeapInit(&heap);
Insert(&heap, 'A', 1);
Insert(&heap, 'B', 2);
Insert(&heap, 'C', 3);
printf("%c \n", Delete(&heap));
Insert(&heap, 'A', 1);
Insert(&heap, 'B', 2);
Insert(&heap, 'C', 3);
printf("%c \n", Delete(&heap));
while (!Empty(&heap))
printf("%c \n", Delete(&heap));
return 0;
}
728x90
반응형
'Data Structure & Algorithm' 카테고리의 다른 글
Flower, Chicken, Cards (0) | 2022.11.14 |
---|---|
[Sort]Bubble, Selection, Insertion (0) | 2022.10.31 |
Expression Tree(merger) (0) | 2022.10.31 |
exp_tree (0) | 2022.10.31 |
Expression Tree (0) | 2022.10.31 |