열혈 자료구조 - 9.2 힙의 구현과 우선순위 큐의 완성(3)

힙 구현의 조정

- 기존의 구조체

    -> 데이터를 입력받을 때 우선순위를 수동적으로 지정해야 했음

    -> 이 구조체를 데이터만을 가지고 우선순위를 비교할 수 있게 하는것이 좋음

typdef char HData;
typdef int Priority;	// 우선 순위

typedef struct _heapElem {
    Priority pr;	// 값이 작을수록 높은 우선순위라고 구현
    HData data;
} HeapElem;		 // 힙에 저장되는 데이터의 기본 단위

typedef struct _heap {
    int numOfData;			// 힙의 개수는 마지막 노드의 번호와 같음
    HeapElem heapArr[HEAP_LEN];
} Heap;			// 힙을 나타내는 구조체

- 변경된 구조체

    -> 데이터를 입력받고 우선순위를 판단하는 함수를 등록

    -> HeapInit 할 때 함수를 등록

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)
{
	ph->numOfData = 0;
	ph->comp = pc;
}

HeapInit(&heap, DataPriorityComp);

 

우선순위 비교 함수

- 반환값은 두 매개변수의 우선순위에 따라 정해진 값을 반환

    -> 첫번째 우선 순위가 높은 경우 음수 반환

    -> 두번째 우선 순위가 높은 경우 양수 반환

    -> 우선 순위가 같은 경우 0 반환

int DataPriorityComp(char ch1, char ch2)
{
	return ch2-ch1;		// ch2가 'B'이고 ch1이 'A'이면 양수이므로 두번째 우선순위가 높음
//	return ch1-ch2;
}

- 우선순위 함수 적용

    -> heapArr의 우선순위를 비교하던 방법에서 comp 함수를 통해 heapArr의 데이터를 전달해서 비교하여 결과를 통해 실행

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;
}

 

우선순위 큐의 구현

- 전에 구현한 힙을 토대로 구현

- 힙은 우선순위 큐에 알맞게 구현되어 있어서 그대로 사용하면 됨

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);
}