Priority Queue (최대 힙) (C 언어)

C++ priority queue 함수 정리 및

C priority queue 구현 예시

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_PQ_SIZE 100001

typedef struct _Data {
    int xPos;
    int yPos;
    int pri;
} Data;

typedef struct _priority_queue {
    Data mem[MAX_PQ_SIZE];
    int back;
} priority_queue;

void initPQ(priority_queue *pq);
void initData(Data *);
bool empty(priority_queue *pq);
void pop(priority_queue *pq);
void push(priority_queue *pq, Data);
size_t size(priority_queue *pq);
Data top(priority_queue *pq);
void swapData(Data *, Data *);

int main(void)
{
    char inStr[20];
    Data inData;
    priority_queue *pq = (priority_queue *)malloc(sizeof(priority_queue));
    initPQ(pq);
    initData(&inData);

    while (1) {
        printf("Input Command: ");
        scanf("%s", inStr);

        if (!strcmp(inStr, "empty")) {
            if (empty(pq)) { printf("true\n"); }
            else { printf("false\n"); }
        }
        else if (!strcmp(inStr, "pop")) { pop(pq); }
        else if (!strcmp(inStr, "push")) {
            printf("Input Data: ");
            scanf("%d %d %d", &inData.xPos, &inData.yPos, &inData.pri);
            push(pq, inData);
        }
        else if (!strcmp(inStr, "size")) { printf("%d\n", (int)size(pq)); }
        else if (!strcmp(inStr, "top")) {
            inData = top(pq);
            printf("(%d, %d): %d\n", inData.xPos, inData.yPos, inData.pri);
        }
        else if (!strcmp(inStr, "print")) {
            int cur = 1;

            for (int i = 1; i <= (int)size(pq); i++) {
                if (i >= cur * 2) {
                    printf("\n");
                    cur *= 2;
                }
                printf("(%d, %d): %d\t", pq->mem[i].xPos, pq->mem[i].yPos, pq->mem[i].pri);
            }
            printf("\n");
        }
        else if (!strcmp(inStr, "help")) { printf("empty\npop\npush\nsize\ntop\nprint\nhelp\nexit\n"); }
        else if (!strcmp(inStr, "exit")) { break; }
        else { printf("Unknown Command\n"); }
    }

    free(pq);
    return 0;
}

void initPQ(priority_queue *pq)
{
    for (int i = 0; i < MAX_PQ_SIZE; i++)
        initData(&pq->mem[i]);
    pq->back = 0;
}
void initData(Data *data)
{
    data->xPos = 0;
    data->yPos = 0;
    data->pri = 0;
    return;
}
bool empty(priority_queue *pq)
{
    if (!pq->back) { return true; }
    else { return false; }
}
void pop(priority_queue *pq)
{
    if (empty(pq)) { return; }
    pq->mem[1] = pq->mem[pq->back];    //마지막 노드 루트로 이동
    initData(&pq->mem[pq->back--]);    //마지막 노드 pop
    if (empty(pq)) { return; }

    int curSize = (int)size(pq);
    int parent = 1;
    int child = parent * 2;

    while (child <= curSize) {
        if (child + 1 <= curSize && pq->mem[child].pri < pq->mem[child + 1].pri) { child++; }    //두 자식 중 우선순위가 높은 child 선택

        if (pq->mem[parent].pri < pq->mem[child].pri)    {    //자식의 우선순위가 높으면 부모와 변경
            swapData(&pq->mem[parent], &pq->mem[child]);
            parent = child;
            child = parent * 2;
        }
        else { break; }
    }
    return;
}
void push(priority_queue *pq, Data data)
{
    pq->mem[++pq->back] = data;
    if ((int)size(pq) == 1) { return; }

    int child = pq->back;
    int parent = child / 2;

    while (child != 1) {    //부모가 없을 때까지 반복
        if (pq->mem[parent].pri < pq->mem[child].pri) {
            swapData(&pq->mem[parent], &pq->mem[child]);
            child = parent;
            parent = child / 2;
        }
        else { break; }
    }
    return;
}
size_t size(priority_queue *pq) { return (size_t)pq->back; }
Data top(priority_queue *pq) { return pq->mem[1]; }
void swapData(Data *pData, Data *cData)
{
    Data tmpData;
    tmpData = *pData;
    *pData = *cData;
    *cData = tmpData;
    return;
}