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

+ Recent posts