[자료구조] 우선순위 큐(Priority Queue)와 힙(Heap)

들어간 순서에 상관없이 우선순위가 높은 데이터가 먼저 나온다

[우선순위 큐의 종류]

• 배열을 기반으로 구현하는 방법 (삽입/삭제시 모든 데이터 뒤로 밀거나 당겨야함, 모든 데이터와 우선순위를 비교해야함)
• 연결리스트를 기반으로 구현하는 방법 (모든 데이터와 우선순위를 비교해야함)
• 힙을 이용하는 방법

 

힙 = 완전이진트리 + 모든 노드에 저장된 값은 자식노드에 저장된 값보다 크거나 같음(최대 힙)

 

 

[힙을 이용하여 만드는 우선순위 큐]

 

힙≠우선순위 큐 이다 → 힙은 우선순위 큐 구현에 딱 어울리는 자료구조일 뿐이다.

 

<힙의 특징>

(데이터 추가 방식)
1. 새로운 데이터는 우선순위가 가장 낮다고 가정하고 마지막 위치에 저장함
2. 부모 노드와 비교해서 위치가 바뀌어야 하면 바꿈
3. 제대로 된 위치를 찾을때 까지 반복

(데이터 삭제 방식) → 우선순위 큐의 삭제 = 가장 높은 우선순위의 데이터 삭제
1. 루트노드를 삭제하고 마지막 노드를 루트노드로 옮김
2. 새로운 루트노드를 자식 노드와의 비교를 통해서 둘중 우선순위가 높은 자식노드와 교환하여 제자리를 찾아가게 함

최대 힙의 데이터 추가과정

 

 

힙은 배열 기반으로 구현해야함
➡️ 연결리스트 기반으로 구현하면 새로운 노드를 마지막 위치에 추가하는것이 쉽지않다

 

배열 기반의 이진트리

 

왼쪽 자식노드의 인덱스 값 = 부모노드 인덱스 * 2
오른쪽 자식노드의 인덱스 값 = 부모노드 인덱스 * 2 + 1
부모노드의 인덱스 값 = 자식노드 / 2

 

▶ 힙의 ADT

필요한 기능 : 데이터의 추가/삭제, 힙 초기화, 데이터 empty 여부

void HeapInit(Heap * ph, PriorityComp pc);
int HIsEmpty(Heap * ph);
void HInsert(Heap * ph, HData data); //데이터 추가
HData HDelete(Heap * ph); //데이터 삭제

 

▶ 힙의 구현

 

• 힙을 의미하는 구조체

typedef struct _heap
{
	PriorityComp * comp; //우선순위의 기준을 정하는 함수
	int numOfData;
	HData heapArr[HEAP_LEN]; //데이터를 저장하는 공간
} Heap;

PriorityComp * comp -> 함수 포인터 변수에 사용자가 지정한 우선순위 함수를 받는다

프로그래머가 우선순위의 판단 기준을 힙에 설정할 수 있다
(첫번째 인자가 우선순위 높으면 양수 반환, 두번째 인자가 우선순위 높으면 음수 반환)

 

• 힙 ADT의 구현

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->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(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(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 HInsert(Heap * ph, HData data) -> 새로운 데이터를 마지막 인덱스에 저장하고 부모노드에 있는 데이터는 밑으로 내리되 새로 저장된 데이터는 인덱스값만 갱신하다가 마지막에 삽입

HData HDelete(Heap * ph) -> 마지막 데이터를 일일이 옮겨가면서 값을 내리지 않고 우선순위가 더 높은 자식노드만 위로 올리고 마지막에 제자리에 삽입

▶ 우선순위 큐의 ADT

필요한 기능 : 데이터의 추가/삭제, 우선순위 큐 초기화, 데이터 empty 여부

void PQueueInit(PQueue * ppq, PriorityComp pc);
int PQIsEmpty(PQueue * ppq);
void PEnqueue(PQueue * ppq, PQData data);
PQData PDequeue(PQueue * ppq);

 

▶ 우선순위 큐의 구현 = 힙과 거의 같음

 

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