우선순위 큐(c언어)

• min-heap

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

/* 1. 우선 순위 큐 자료구조 정의*/
typedef struct s_minpq
{
    int *data; // 힙을 저장할 동적 배열
    int capacity; // 할당된 배열 크기
    int size; // 현재 힙에 들어있는 원소 갯수
}   t_minpq;

/* 2. 헬퍼 함수: 인덱스 계산*/
// 부모 노드 인덱스
static inline int parent(int i)
{
    return (i - 1) / 2;
}
// 왼쪽 자식 인덱스
static inline int left(int i)
{
    return 2 * i + 1;
}
// 오른쪽 자식 인덱스
static inline int right(int i)
{
    return 2 * i + 2;
}

/* 3. 큐 생성 및 해제 */
t_minpq    *create_minpq(int capacity)
{
    t_minpq *pq = malloc(sizeof(*pq));

    if (!pq)
        return NULL;
    pq->capacity = capacity;
    pq->size = 0;
    pq->data = malloc(sizeof(int) * capacity);
    if (!pq->data)
    {
        free(pq);
        return (NULL);
    }
    return pq;
}

void free_minpq(t_minpq *pq)
{
    if (pq)
    {
        free(pq->data);
        free(pq);
    }
}

/* 4. 내부 연산: 힙 속성 유지용 swap*/
static void swap(int *a, int *b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

/* 5. 삽입
 * 새 원소를 맨 끝에 추가한 뒤
 * 부모와 비교하며 위로 올린다.
 */
void push_minpq(t_minpq *pq, int value)
{
    if (pq->size == pq->capacity)
    {
        pq->capacity *= 2;
        pq->data = realloc(pq->data, sizeof(int) * pq->capacity);
    }
    // 1) 배열 맨 끝에 추가
    int i = pq->size++;
    pq->data[i] = value;

    // 2) 부모와 비교하며 최소 힙 속성 유지
    while (i != 0 && pq->data[parent(i)] > pq->data[i])
    {
        swap(&pq->data[i], &pq->data[parent(i)]);
        i = parent(i);
    }
}

/* 6.제거
 *  최소값을 꺼내고,
 *  맨 끝 원소를 루트에 옮긴 후
 *  자식들과 비교하여 아래로 내린다
 */
int pop_minpq(t_minpq *pq)
{
    int i;
    int small;

    if (pq->size <= 0)
        return (INT_MAX); // 빈 큐 처리
    i = 0;
    small = pq->data[0];
    // 1) 마지막 원소를 루트로 이동
    pq->data[0] = pq->data[--pq->size];
    while (1)
    {
        int l = left(i);
        int r = right(i);
        int s = i;

        if (l < pq->size && pq->data[l] < pq->data[s])
            s = l;
        if (r < pq->size && pq->data[r] < pq->data[s])
            s = r;
        if (s == i)
                break;
        swap(&pq->data[i], &pq->data[s]);
        i = s;
    }
    return (small);
}



int main(void)
{
    t_minpq *pq = create_minpq(4);

    push_minpq(pq, 10);
    push_minpq(pq, 5);
    push_minpq(pq, 20);
    push_minpq(pq, 1);

    while (pq->size > 0)
    {
        printf("%d ", pop_minpq(pq));
    }
    free_minpq(pq);
    return 0;
}