#define PQ_SIZE 1000
typedef int item_type;

struct priority_queue {
        item_type q[PQ_SIZE + 1];
        int n;
};

int pq_parent(int n)
{
        if(n == 1)
                return -1;
        else
                return n / 2;
}

int pq_young_child(int n)
{
        return 2 * n;
}

void pq_swap(struct priority_queue *q, int a, int b)
{
        int c = q->q[a];
        q->q[a] = q->q[b];
        q->q[b] = c;
}

void bubble_up(struct priority_queue *q, int p)
{
        if(pq_parent(p) == -1)  /* at root of heap, no parent */
                return;
        if(q->q[pq_parent(p)] > q->q[p]) {
                pq_swap(q, p, pq_parent(p));
                bubble_up(q, pq_parent(p));
        }
}


void pq_insert(struct priority_queue *q, item_type x)
{
        if (q->n >= PQ_SIZE)
                printf("Warning: priority queue overflow insert x=%d\n", x);
        else {
                q->n = (q->n) + 1;
                q->q[q->n] = x;
                bubble_up(q, q->n);
        }
}

void pq_init(struct priority_queue *q)
{
        q->n = 0;
}

void make_heap(struct priority_queue *q, item_type s[], int n)
{

        pq_init(q);
        for(int i = 0; i < n; ++i)
                pq_insert(q, s[i]);
}

void bubble_down(struct priority_queue *q, int p)
{
        int c; /* child index */
        int i; /* counter */
        int min_index; /* index of lightest child */

        c = pq_young_child(p);
        min_index = p;

        for(i = 0; i <= 1; ++i)
                if ((c + i) <= q->n)
                        if(q->q[min_index] > q->q[c + i])
                                min_index = c + i;

        if (min_index != p) {
                pq_swap(q, p, min_index);
                bubble_down(q, min_index);
        }
}

item_type extract_min(struct priority_queue *q)
{
        int min; /* minimum value */

        if (q->n <= 0)
                printf("Warning: empty priority queue.\n");
        else {
                min = q->q[1];

                q->q[1] = q->q[q->n];
                --q->n;
                bubble_down(q,1);
        }

        return min;
}