public
Created

  • Download Gist
skiena_heapsort.c
C
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86
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; i<n; i++)
pq_insert(q, s[i]);
}
 
item_type extract_min(priority_queue *q) {
int min = -1;
if (q->n <= 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<n; i++)
s[i] = extract_min(&q);
}

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.