C언어 우선순위큐 구현

1 개요

C언어 우선순위큐 구현
#include <stdio.h>

#define MAX_N 100

int heap[MAX_N];
int heapSize = 0;

void clear() {
    heapSize = 0;
}

int empty() {
    return heapSize == 0;
}

void push(int value) {
    if (heapSize + 1 > MAX_N) {
        printf("overflow!!!");
        return;
    }
    heap[heapSize] = value;
    int current = heapSize;
    while (current > 0 && heap[current] < heap[(current - 1) / 2]) {
        int temp = heap[(current - 1) / 2];
        heap[(current - 1) / 2] = heap[current];
        heap[current] = temp;
        current = (current - 1) / 2;
    }
    heapSize += 1;
}

int pop() {
    if (heapSize <= 0) {
        printf("empty!!!");
        return 0;
    }
    int value = heap[0];
    heapSize -= 1;
    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] < heap[current * 2 + 2]
                        ? current * 2 + 1
                        : current * 2 + 2;
        }
        if (heap[current] < heap[child]) break;
        int temp = heap[current];
        heap[current] = heap[child];
        heap[child] = temp;
        current = child;
    }
    return value;
}

int main() {
    push(7);
    push(5);
    push(3);
    push(9);
    push(5);
    push(1);
    while (!empty()) {
        printf("%d ", pop());  // 1 3 5 5 7 9 
    }
    pop(); // empty!!!
}
2 같이 보기
