[자료구조] 우선순위 큐와 힙 - 03 . 우선순위 큐 구현

[우선순위 큐 구현]

[PQ.h]

#ifndef PQ_H
#define PQ_H

#include<stdio.h>
#include<stdlib.h>
#include<memory.h>

typedef int PriorityType;

//노드 (우선순위가 추가됨)
typedef struct tagPQNode
{
	PriorityType Priority;
	void* Data;
}PQNode;

//우선순위 큐
typedef struct tagPriorityQueue
{
	PQNode* Nodes;
	int Capacity;
	int UsedSize;
}PriorityQueue;

//큐의 생성
PriorityQueue* PQ_Create(int Initialize);

//큐의 삭제
void PQ_Destroy(PriorityQueue* PQ);

//노드의 삽입
void PQ_Enqueue(PriorityQueue* PQ, PQNode NewData);

//노드의 삭제
void PQ_Dequeue(PriorityQueue* PQ, PQNode* Root);

//부모 얻기
int PQ_GetParent(int Index);

//왼쪽 자식 얻기
int PQ_GetLeftChild(int Index);

//노드 교환
void PQ_SwapNodes(PriorityQueue* PQ, int Index1, int Index2);

//큐 비었는지 판단
int PQ_IsEmpty(PriorityQueue* PQ);



#endif

 

[PQ.cpp]

#include"PQ.h"

//큐의 생성
PriorityQueue* PQ_Create(int Initialize)
{
	PriorityQueue* NewPQ = (PriorityQueue*)malloc(sizeof(PriorityQueue));
	NewPQ->Capacity = Initialize;
	NewPQ->UsedSize = 0;
	NewPQ->Nodes = (PQNode*)malloc(sizeof(PQNode) * Initialize);
	return NewPQ;
}

//큐의 삭제
void PQ_Destroy(PriorityQueue* PQ)
{
	free(PQ->Nodes);
	free(PQ);
}

//노드의 삽입
//(1 .삽입위치 , 부모위치 찾음 -> 2 . 용량 확인후 필요하면 확장 -> 3 . 삽입 -> 4 . 힙 순서 속성 만족까지 부모와 교환 -> 5. 사용용량 ++)
void PQ_Enqueue(PriorityQueue* PQ, PQNode NewData)
{
	int CurrentPosition = PQ->UsedSize;
	int ParentPosition = PQ_GetParent(CurrentPosition);

	//큐가 가득 찼다면 용량을 2배 늘려준다
	if (PQ->UsedSize == PQ->Capacity)
	{
		if (PQ->Capacity == 0)
			PQ->Capacity = 1;

		PQ->Capacity *= 2;
		PQ->Nodes = (PQNode*)realloc(PQ->Nodes,sizeof(PQ->Nodes) * PQ->Capacity);
	}

	PQ->Nodes[CurrentPosition] = NewData;

	//힙 순서 속성을 만족할때까지 교환을 진행한다 .
	while (CurrentPosition > 0 && PQ->Nodes[CurrentPosition].Priority < PQ->Nodes[ParentPosition].Priority)
	{
		PQ_SwapNodes(PQ,CurrentPosition, ParentPosition);

		CurrentPosition = ParentPosition;
		ParentPosition = PQ_GetParent(CurrentPosition);
	}
	PQ->UsedSize++;
}

//노드의 삭제
//(1 . Root에 PQ의 루트 값을 넣고 , 루트에 0을 넣어 잎노드 최 우측 자식과 위치를 바꾼다 2.자식의 위치를 구한다
// 3 . 자식을 비교 우선순위가 높은 자식과 비교를 진행한다 4.부모보다 자식의 우선순위가 높다면 교환한다(힙 순서 속성 만족까지))
// 5 . 교환후 사용 사이즈가 용량의 반이 안된다면 줄여준다
void PQ_Dequeue(PriorityQueue* PQ, PQNode* Root)
{
	int ParentPosition = 0;
	int LeftPosition = 0;
	int RightPosition = 0;

	memcpy(Root, &PQ->Nodes[0], sizeof(PQNode));
	memset(&PQ->Nodes[0], 0, sizeof(PQNode));

	PQ->UsedSize--;
	PQ_SwapNodes(PQ, 0, PQ->UsedSize);

	LeftPosition = PQ_GetLeftChild(0);
	RightPosition = LeftPosition + 1;

	//힙 우선 속성 만족까지 교환을 진행
	while (1)
	{
		int SelectedChild = 0;

		if (LeftPosition >= PQ->UsedSize)
			break;

		if (RightPosition >= PQ->UsedSize)
		{
			SelectedChild = LeftPosition;
		}
		else
		{
			//우선 순위는 값이 작을수록 우선순위가 높은 것이다
			SelectedChild = PQ->Nodes[LeftPosition].Priority < PQ->Nodes[RightPosition].Priority ? LeftPosition : RightPosition;
		}

		//부모 우선순위가 더 낮다면(값이 크다면)
		if (PQ->Nodes[ParentPosition].Priority > PQ->Nodes[SelectedChild].Priority)
		{
			PQ_SwapNodes(PQ, ParentPosition, SelectedChild);
			ParentPosition = SelectedChild;
		}
		else
			break;

		LeftPosition = PQ_GetLeftChild(ParentPosition);
		RightPosition = LeftPosition + 1;
	}

	//크기를 재할당
	if ((PQ->Capacity / 2) > PQ->UsedSize)
	{
		PQ->Capacity /= 2;
		PQ->Nodes = (PQNode*)realloc(PQ->Nodes, sizeof(PQNode) * PQ->Capacity);
	}

}

//부모 얻기
int PQ_GetParent(int Index)
{
	return (int)((Index - 1) / 2);
}

//왼쪽 자식 얻기
int PQ_GetLeftChild(int Index)
{
	return (Index*2) + 1;
}

//노드 교환
void PQ_SwapNodes(PriorityQueue* PQ, int Index1, int Index2)
{
	int CopySize = sizeof(PQNode);
	PQNode* Temp = (PQNode*)malloc(CopySize);

	memcpy(Temp, &PQ->Nodes[Index1], CopySize);
	memcpy(&PQ->Nodes[Index1], &PQ->Nodes[Index2], CopySize);
	memcpy(&PQ->Nodes[Index2],Temp, CopySize);

	free(Temp);
}

//큐 비었는지 판단
int PQ_IsEmpty(PriorityQueue* PQ)
{
	return PQ->UsedSize == 0;
}

[Test.cpp]

#include"PQ.h"

void PrintNode(PQNode* Node)
{
	printf("작업명 : %s (우선순위 : %d)\n", Node->Data, Node->Priority);
}

int main(void)
{
	PriorityQueue* PQ = PQ_Create(3);
	PQNode Popped;

	PQNode Nodes[7] = {
		{34,(void*)"코딩"},
		{12,(void*)"커피미팅"},
		{87,(void*)"커피타기"},
		{45,(void*)"문서작성"},
		{35,(void*)"디버깅"},
		{66,(void*)"이닦기"},
	};

	PQ_Enqueue(PQ, Nodes[0]);
	PQ_Enqueue(PQ, Nodes[1]);
	PQ_Enqueue(PQ, Nodes[2]);
	PQ_Enqueue(PQ, Nodes[3]);
	PQ_Enqueue(PQ, Nodes[4]);
	PQ_Enqueue(PQ, Nodes[5]);

	printf("큐에 남아있는 작업의 수 : %d\n", PQ->UsedSize);

	while (!PQ_IsEmpty(PQ))
	{
		PQ_Dequeue(PQ, &Popped);
		PrintNode(&Popped);
	}
	return 0;

}