[C] Priority Queue

           

 ※ 오름차순 정렬

// file: priority_queue.c
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

struct data {
    int val;
};

/* 실제 데이터를 담는 배열 */
struct data input[MAX_SIZE];

/* 힙은 데이터의 포인터만을 담는 배열 */
struct data* heap[MAX_SIZE];
int heapSize = 0;

void heapInit(void)
{
    heapSize = 0;
}

int heapPush(struct data* node)
{
    if (heapSize >= MAX_SIZE)
    {
        printf("queue is full!");
        return 0;
    }

    heap[heapSize] = node;

    int current = heapSize;
    while (current > 0 && heap[current]->val < heap[(current - 1) / 2]->val)
    {
        struct data* temp = heap[(current - 1) / 2];
        heap[(current - 1) / 2] = heap[current];
        heap[current] = temp;

        current = (current - 1) / 2;
    }

    heapSize = heapSize + 1;

    return 1;
}

int heapPop(int* value)
{
    if (heapSize <= 0)
    {
        return -1;
    }

    struct data* popped = heap[0];
    *value = popped->val;

    heapSize = heapSize - 1;

    if (heapSize > 0)
    {
        heap[0] = heap[heapSize];
    }

    int current = 0;
    while (current * 2 + 1 < heapSize)
    {
        int child;
        if (current * 2 + 2 == heapSize)
        {
            child = current * 2 + 1;
        }
        else
        {
            child = heap[current * 2 + 1]->val < heap[current * 2 + 2]->val
                ? current * 2 + 1
                : current * 2 + 2;
        }

        if (heap[current]->val < heap[child]->val)
        {
            break;
        }

        struct data* temp = heap[current];
        heap[current] = heap[child];
        heap[child] = temp;

        current = child;
    }

    return 1;
}

int main(int argc, char* argv[])
{
    int N = 10;

    for (int i = 0; i < N; i++)
    {
        input[i].val = rand();
        heapPush(&input[i]);
    }

    for (int i = 0; i < N; i++)
    {
        int value;
        heapPop(&value);
        printf("%d ", value);
    }
    printf("\n");
    return 0;
}

           

 

※ 내림차순 정렬

// file: priority_queue.c
#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

struct data {
    int val;
};

/* 실제 데이터를 담는 배열 */
struct data input[MAX_SIZE];

/* 힙은 데이터의 포인터만을 담는 배열 */
struct data* heap[MAX_SIZE];
int heapSize = 0;

void heapInit(void)
{
    heapSize = 0;
}

int heapPush(struct data* node)
{
    if (heapSize >= MAX_SIZE)
    {
        printf("queue is full!");
        return 0;
    }

    heap[heapSize] = node;

    int current = heapSize;
    while (current > 0 && heap[current]->val > heap[(current - 1) / 2]->val)
    {
        struct data* temp = heap[(current - 1) / 2];
        heap[(current - 1) / 2] = heap[current];
        heap[current] = temp;

        current = (current - 1) / 2;
    }

    heapSize = heapSize + 1;

    return 1;
}

int heapPop(int* value)
{
    if (heapSize <= 0)
    {
        return -1;
    }

    struct data* popped = heap[0];
    *value = popped->val;

    heapSize = heapSize - 1;

    if (heapSize > 0)
    {
        heap[0] = heap[heapSize];
    }

    int current = 0;
    while (current * 2 + 1 < heapSize)
    {
        int child;
        if (current * 2 + 2 == heapSize)
        {
            child = current * 2 + 1;
        }
        else
        {
            child = heap[current * 2 + 1]->val > heap[current * 2 + 2]->val
                ? current * 2 + 1
                : current * 2 + 2;
        }

        if (heap[current]->val >= heap[child]->val)
        {
            break;
        }

        struct data* temp = heap[current];
        heap[current] = heap[child];
        heap[child] = temp;

        current = child;
    }

    return 1;
}

int main(int argc, char* argv[])
{
    int N = 10;

    for (int i = 0; i < N; i++)
    {
        input[i].val = rand();
        heapPush(&input[i]);
    }

    for (int i = 0; i < N; i++)
    {
        int value;
        heapPop(&value);
        printf("%d ", value);
    }
    printf("\n");
    return 0;
}