Instantly share code, notes, and snippets.

# ikr/skiena_heapsort.c Created Mar 31, 2011

What would you like to do?
 typedef struct { item_type q[PQ_SIZE+1]; /* body of queue */ int n; /* number of queue elements */ } priority_queue; pq_parent(int n) { if (n == 1) return(-1); else return((int) n/2); } pq_young_child(int n) { return(2 * n); } pq_insert(priority_queue *q, item_type x) { if (q->n >= PQ_SIZE) printf("Overflow on x = %d\n", x); else { q->n = (q->n) + 1; q->q[ q->n ] = x; bubble_up(q, q->n); } } bubble_up(priority_queue *q, int p){ if (pq_parent(p) == -1) return; if (q->q[pq_parent(p)] > q->q[p]) { pq_swap(q,p,pq_parent(p)); bubble_up(q, pq_parent(p)); } } pq_init(priority_queue *q) { q->n = 0; } make_heap(priority_queue *q, item_type s[], int n) { int i; pq_init(q); for (i=0; in <= 0) printf("Empty queue\n"); else { min = q->q[1]; q->q[1] = q->q[ q->n ]; q->n = q->n - 1; bubble_down(q,1); } return(min); } bubble_down(priority_queue *q, int p) { int c; int i; int min_index; 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); } } heapsort(item_type s[], int n){ int i; priority_queue q; make_heap(&q,s,n); for (i=0; i