pq_c.c

#include <stdio.h>

struct node {
    int weight;
};

struct PriorityQueue {
    struct node n[65];
    int cnt;
};

struct PriorityQueue pq;

void print() {
    int i;
    int t = 2;
    for (i = 1; i <= 64; i++) {
        printf("%d ", pq.n[i].weight);
        if (i % (t - 1) == 0) {
            printf("\n");
            t *= 2;
        }
    }
    printf("\n==============================\n");
}

void swap(struct node *n1, struct node *n2) {
    struct node tmp;
    tmp.weight = n1->weight;
    n1->weight = n2->weight;
    n2->weight = tmp.weight;
}

void shiftup(int index) {
    if (index <= 1) return ;
    int parent = index >> 1;
    if (pq.n[index].weight < pq.n[parent].weight) {
        swap(&pq.n[index / 2], &pq.n[index]);
        shiftup(parent);
    }
}

void shiftdown(int index) {
    int l = index * 2;
    int r = index * 2 + 1;
    int imin = index;

    if (l <= pq.cnt && pq.n[l].weight < pq.n[imin].weight) {
        imin = l;
    }
    if (r <= pq.cnt && pq.n[r].weight < pq.n[imin].weight) {
        imin = r;
    }
    if (imin == index) return ;
    swap(&pq.n[imin], &pq.n[index]);
    shiftdown(imin);
}

void push(int _weight) {
    pq.cnt++;
    pq.n[pq.cnt].weight = _weight;
    shiftup(pq.cnt);
}

void pop() {
    if (pq.cnt == 0) return ;
    swap(&pq.n[1], &pq.n[pq.cnt]);
    pq.n[pq.cnt].weight = 0;
    pq.cnt--;
    shiftdown(1);
}

void init() {
    pq.cnt = 0;
}

int main() {
    init();
    int op, num;
    while (1) {
        scanf("%d", &op);
        if (op == 0) {
            scanf("%d", &num);
            push(num);
        } else pop();
        print();
    }
    return 0;
}