자료구조 PriorityQueue

//PriorityQueue.h 헤더파일 만들기

#ifndef PRIORITYQUEUE_H
#define PRIORITYQUEUE_H

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

typedef int PriorityType;

typedef struct tagPQNode {
        PriorityType Priority;
        void* Data;
}PQNode;

typedef struct tagPriorityQueue {
        PQNode* Nodes;
        int Capacity;
        int UsedSize;
}PriorityQueue;

PriorityQueue* Create(int InitialSize);
void Destroy(PriorityQueue* PQ);
void Enqueue(PriorityQueue* PQ, PQNode NewData);
void Dequeue(PriorityQueue* PQ, PQNode* Root);
int GetParent(int index);
int GetLeftChild(int index);
void SwapNodes(PriorityQueue* PQ, int Index1, int Index2);
void PrintNode(PriorityQueue* PQ);
int IsEmpty(PriorityQueue* PQ);

#endif

================================================================================

#include "PriorityQueue.h"

PriorityQueue* Create(int InitialSize){
        PriorityQueue* NewPQ = (PriorityQueue*)malloc(sizeof(PriorityQueue));
        NewPQ ->Capacity = InitialSize;
        NewPQ ->UsedSize = 0;
        NewPQ ->Nodes = (PQNode*)malloc(sizeof(PQNode)*NewPQ ->Capacity);

        printf("size : %d\n", sizeof(PQNode));

        return NewPQ ;
}

void Destroy(PriorityQueue* PQ){
        free(PQ->Nodes);
        free(PQ);
}

void Enqueue(PriorityQueue* PQ, PQNode NewNode){
        int CurrentPosition = PQ->UsedSize;
        int ParentPosition = GetParent(CurrentPosition);

        if (PQ->UsedSize == PQ ->Capacity) {
                PQ->Capacity *= 2;
                PQ->Nodes = (PQNode*)realloc(PQ->Nodes, sizeof(PQNode)*PQ->Capacity);
        }
        PQ->Nodes[CurrentPosition] = NewNode;

        while (PQ->Nodes[CurrentPosition].Priority < PQ->Nodes[ParentPosition].Priority) {
                SwapNodes(PQ, CurrentPosition, ParentPosition);

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

void 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--;
        SwapNodes(PQ, 0, PQ->UsedSize);

        LeftPosition = GetLeftChild(0);
        RightPosition = LeftPosition + 1;
        while (1) {
                int SelectedChild = 0;
                //자식이 없는 경우
                if (LeftPosition >= PQ->UsedSize) break;

                //오른쪽에 자식이 없는 경우(왼쪽에만 있는 경우)
                if (RightPosition >= PQ->UsedSize)
                        SelectedChild = LeftPosition;
                else { //양쪽 모두 자식이 있는 경우
                        if (PQ->Nodes[LeftPosition].Priority > PQ->Nodes[RightPosition].Priority)
                                SelectedChild = RightPosition;
                        else SelectedChild = LeftPosition;
                }

                if (PQ->Nodes[ParentPosition].Priority > PQ->Nodes[SelectedChild].Priority) {
                        SwapNodes(PQ, ParentPosition, SelectedChild);
                ParentPosition = SelectedChild;
                }
                else {
                        break;
                }
                LeftPosition = GetLeftChild(ParentPosition);
                RightPosition = LeftPosition + 1;
}
        if (PQ->UsedSize < (PQ->Capacity) / 2) {
                PQ->Capacity /= 2;
        }
}

int GetParent(int index) {
        return (index - 1) / 2;
}

int GetLeftChild(int index){
        return (2 * index) + 1;
}

void 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[Index1], Temp, CopySize);
        free(Temp);
}

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

int IsEmpty(PriorityQueue* PQ){
        return (PQ->UsedSize == 0);
}

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

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

        for (int i = 0; i < 6; i++) {
                Enqueue(PQ, Nodes[i]);
        }
        printf("큐에 남아 있는 작업의 수 : %d\n", PQ->UsedSize);

        while (!IsEmpty(PQ)) {
                Dequeue(PQ, &Popped);
                PrintNode(&Popped);
        }
}