"C언어 우선순위큐 구현"의 두 판 사이의 차이

10번째 줄: 10번째 줄:
int heapSize = 0;
int heapSize = 0;


void clear() { heapSize = 0; }
void clear() {
    heapSize = 0;
}


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


void push(int value) {
void push(int value) {
     if (heapSize + 1 > MAX_N) {
     if (heapSize + 1 > MAX_N) {
         printf("Error: overflow!");
         printf("overflow!!!");
         return;
         return;
     }
     }
32번째 줄: 36번째 줄:
int pop() {
int pop() {
     if (heapSize <= 0) {
     if (heapSize <= 0) {
         printf("Error: empty!");
         printf("empty!!!");
         return 0;
         return 0;
     }
     }
57번째 줄: 61번째 줄:
}
}


int main(int argc, char* argv[]) {
int main() {
     push(5);
     push(5);
     push(3);
     push(3);
65번째 줄: 69번째 줄:
         printf("%d ", pop());  // 0 3 5 9
         printf("%d ", pop());  // 0 3 5 9
     }
     }
     pop();  // Error: empty!
     pop();  // empty!!!
}
}
</syntaxhighlight>
</syntaxhighlight>

2024년 2월 3일 (토) 18:18 판

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(5);
    push(3);
    push(9);
    push(0);
    while (!empty()) {
        printf("%d ", pop());  // 0 3 5 9
    }
    pop();  // empty!!!
}

2 같이 보기

문서 댓글 ({{ doc_comments.length }})
{{ comment.name }} {{ comment.created | snstime }}