[백준] 11279번 최대 힙 (= maximum heap) - 재우스 프로그래밍 (C 언어)

문제 링크 :www.acmicpc.net/problem/11279

 

알고리즘 : 우선순위 큐 zeus-programming.tistory.com/65

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

비슷한 문제 : 최소 힙 zeus-programming.tistory.com/67

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

#define DEBUG 1
#define MAX_PQ_SIZE 100001

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

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

int main(void)
{
    int N = 0;    //연산의 개수
    int x = 0;    //입력 받은 연산 정보
    priority_queue *pq = (priority_queue *)malloc(sizeof(priority_queue));

    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d" ,&x);
        if (x) { push(pq, x); }
        else {
            printf("%d\n", top(pq));
            pop(pq);
        }
    }

    free(pq);
    return 0;
}

void initPQ(priority_queue *pq)
{
    for (int i = 0; i < MAX_PQ_SIZE; i++)
        pq->mem[i] = 0;
    pq->back = 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];
    pq->mem[pq->back--] = 0;
    if (empty(pq)) { return; }

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

    while (child <= pqSize) {
        if (child + 1 <= pqSize && pq->mem[child] < pq->mem[child + 1])
            child++;

        if (pq->mem[parent] < pq->mem[child]) {
            swapData(&pq->mem[parent], &pq->mem[child]);
            parent = child;
            child = parent * 2;
        }
        else { break; }
    }
    return;
}
void push(priority_queue *pq, int 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] < pq->mem[child]) {
            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; }
int top(priority_queue *pq) { return pq->mem[1]; }
void swapData(int *pData, int *cData)
{
    int temp = 0;
    temp = *pData;
    *pData = *cData;
    *cData = temp;
    return;
}