|
=={{header|C}}==
Using a dynamic array as a binary heap. Stores integer priority and a void datacharacter pointer. There's no limit on heap size besides integer overflow, although a very large heap will cause a lot of page faults. Supports insert, extraction, peeking at top element, mergingpush and clearingpop.
<lang c>#include <stdio.h>
#include <stdlib.h>
typedef struct { void * data; int pri; } q_elem_t;
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 */
pri_queue priq_new( 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));
q if (h->buflen =+ malloc(sizeof(q_elem_t)1 *>= h->size); {
q h->allocsize = 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) {
qh->allocnodes[1] *= 2h->nodes[h->len];
h->len--;
b = q->buf = realloc(q->buf, sizeof(q_elem_t) * q->alloc);
} else i = 1;
bwhile =(1) q->buf;{
k = i;
n j = q->n++2 * i;
if (j <= h->len && h->nodes[j].priority < h->nodes[k].priority) {
/* append at end, then up heap */
while ((m = n / 2) && pri < b[m].pri) {k = j;
b[n] = b[m]; }
if (j + 1 <= h->len && h->nodes[j + 1].priority < h->nodes[k].priority) {
n = m;
k = j + 1;
}
b[n].data = data; }
b[n].pri if (k == i) pri;{
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;
if push(q->nh, ==5, 1)"Make return 0tea");
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++}}==
| 