Priority queue: Difference between revisions
Content added Content deleted
m (→{{header|Run BASIC}}: {{out}}) |
(→{{header|C}}: reduce the scope of the answer) |
||
Line 195: | Line 195: | ||
=={{header|C}}== |
=={{header|C}}== |
||
Using a dynamic array as a binary heap. Stores integer priority and a |
Using a dynamic array as a binary heap. Stores integer priority and a character pointer. Supports push and pop. |
||
<lang c>#include <stdio.h> |
<lang c>#include <stdio.h> |
||
#include <stdlib.h> |
#include <stdlib.h> |
||
typedef struct { |
typedef struct { |
||
int priority; |
|||
typedef struct { q_elem_t *buf; int n, alloc; } pri_queue_t, *pri_queue; |
|||
char *data; |
|||
} node_t; |
|||
typedef struct { |
|||
#define priq_purge(q) (q)->n = 1 |
|||
node_t *nodes; |
|||
#define priq_size(q) ((q)->n - 1) |
|||
int len; |
|||
/* first element in array not used to simplify indices */ |
|||
int size; |
|||
} heap_t; |
|||
{ |
|||
if (size < 4) size = 4; |
|||
void push (heap_t *h, int priority, char *data) { |
|||
pri_queue q = malloc(sizeof(pri_queue_t)); |
|||
if (h->len + 1 >= h->size) { |
|||
h->size = h->size ? h->size * 2 : 4; |
|||
h->nodes = realloc(h->nodes, h->size * sizeof (node_t)); |
|||
q->n = 1; |
|||
} |
|||
int i = h->len + 1; |
|||
return q; |
|||
int j = i / 2; |
|||
while (i > 1 && h->nodes[j].priority > priority) { |
|||
h->nodes[i] = h->nodes[j]; |
|||
i = j; |
|||
j = j / 2; |
|||
} |
|||
h->nodes[i].priority = priority; |
|||
h->nodes[i].data = data; |
|||
h->len++; |
|||
} |
} |
||
char *pop (heap_t *h) { |
|||
void priq_push(pri_queue q, void *data, int pri) |
|||
int i, j, k; |
|||
{ |
|||
if (!h->len) { |
|||
q_elem_t *b; |
|||
return NULL; |
|||
int n, m; |
|||
} |
|||
char *data = h->nodes[1].data; |
|||
if (q->n >= q->alloc) { |
|||
h->nodes[1] = h->nodes[h->len]; |
|||
h->len--; |
|||
b = q->buf = realloc(q->buf, sizeof(q_elem_t) * q->alloc); |
|||
i = 1; |
|||
while (1) { |
|||
k = i; |
|||
j = 2 * i; |
|||
if (j <= h->len && h->nodes[j].priority < h->nodes[k].priority) { |
|||
/* append at end, then up heap */ |
|||
k = j; |
|||
} |
|||
if (j + 1 <= h->len && h->nodes[j + 1].priority < h->nodes[k].priority) { |
|||
n = m; |
|||
k = j + 1; |
|||
} |
|||
} |
|||
if (k == i) { |
|||
break; |
|||
} |
|||
h->nodes[i] = h->nodes[k]; |
|||
i = k; |
|||
} |
|||
h->nodes[i] = h->nodes[h->len + 1]; |
|||
return data; |
|||
} |
} |
||
int main () { |
|||
/* remove top item. returns 0 if empty. *pri can be null. */ |
|||
heap_t *h = calloc(1, sizeof (heap_t)); |
|||
void * priq_pop(pri_queue q, int *pri) |
|||
push(h, 3, "Clear drains"); |
|||
{ |
|||
push(h, 4, "Feed cat"); |
|||
void *out; |
|||
push(h, 5, "Make tea"); |
|||
push(h, 1, "Solve RC tasks"); |
|||
push(h, 2, "Tax return"); |
|||
q_elem_t *b = q->buf; |
|||
int i; |
|||
for (i = 0; i < 5; i++) { |
|||
out = b[1].data; |
|||
printf("%s\n", pop(h)); |
|||
if (pri) *pri = b[1].pri; |
|||
} |
|||
return 0; |
|||
/* pull last item to top, then down heap. */ |
|||
--q->n; |
|||
int n = 1, m; |
|||
while ((m = n * 2) < q->n) { |
|||
if (m + 1 < q->n && b[m].pri > b[m + 1].pri) m++; |
|||
if (b[q->n].pri <= b[m].pri) break; |
|||
b[n] = b[m]; |
|||
n = m; |
|||
} |
|||
b[n] = b[q->n]; |
|||
if (q->n < q->alloc / 2 && q->n >= 16) |
|||
q->buf = realloc(q->buf, (q->alloc /= 2) * sizeof(b[0])); |
|||
return out; |
|||
} |
} |
||
</lang> |
|||
{{output}} |
|||
/* get the top element without removing it from queue */ |
|||
<pre>Solve RC tasks |
|||
void* priq_top(pri_queue q, int *pri) |
|||
Tax return |
|||
{ |
|||
Clear drains |
|||
if (q->n == 1) return 0; |
|||
Feed cat |
|||
if (pri) *pri = q->buf[1].pri; |
|||
Make tea</pre> |
|||
return q->buf[1].data; |
|||
} |
|||
/* this is O(n log n), but probably not the best */ |
|||
void priq_combine(pri_queue q, pri_queue q2) |
|||
{ |
|||
int i; |
|||
q_elem_t *e = q2->buf + 1; |
|||
for (i = q2->n - 1; i >= 1; i--, e++) |
|||
priq_push(q, e->data, e->pri); |
|||
priq_purge(q2); |
|||
} |
|||
int main() |
|||
{ |
|||
int i, p; |
|||
const char *c, *tasks[] ={ |
|||
"Clear drains", "Feed cat", "Make tea", "Solve RC tasks", "Tax return" }; |
|||
int pri[] = { 3, 4, 5, 1, 2 }; |
|||
/* make two queues */ |
|||
pri_queue q = priq_new(0), q2 = priq_new(0); |
|||
/* push all 5 tasks into q */ |
|||
for (i = 0; i < 5; i++) |
|||
priq_push(q, tasks[i], pri[i]); |
|||
/* pop them and print one by one */ |
|||
while ((c = priq_pop(q, &p))) |
|||
printf("%d: %s\n", p, c); |
|||
/* put a million random tasks in each queue */ |
|||
for (i = 0; i < 1 << 20; i++) { |
|||
p = rand() / ( RAND_MAX / 5 ); |
|||
priq_push(q, tasks[p], pri[p]); |
|||
p = rand() / ( RAND_MAX / 5 ); |
|||
priq_push(q2, tasks[p], pri[p]); |
|||
} |
|||
printf("\nq has %d items, q2 has %d items\n", priq_size(q), priq_size(q2)); |
|||
/* merge q2 into q; q2 is empty */ |
|||
priq_combine(q, q2); |
|||
printf("After merge, q has %d items, q2 has %d items\n", |
|||
priq_size(q), priq_size(q2)); |
|||
/* pop q until it's empty */ |
|||
for (i = 0; (c = priq_pop(q, 0)); i++); |
|||
printf("Popped %d items out of q\n", i); |
|||
return 0; |
|||
}</lang> |
|||
{{out}} |
|||
<pre>1: Solve RC tasks |
|||
2: Tax return |
|||
3: Clear drains |
|||
4: Feed cat |
|||
5: Make tea |
|||
q has 1048576 items, q2 has 1048576 items |
|||
After merge, q has 2097152 items, q2 has 0 items |
|||
Popped 2097152 items out of q</pre> |
|||
=={{header|C++}}== |
=={{header|C++}}== |