Priority queue: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) m (→{{header|Sidef}}: Fix link: Perl 6 --> Raku) |
|||
Line 754:
Feed cat
Make tea</pre>
=== Pairing heap w/ generic data types ===
header file:
<lang C>
typedef struct _pq_node_t {
long int key;
struct _pq_node_t *next, *down;
} pq_node_t, *heap_t;
extern heap_t heap_merge(heap_t, heap_t);
extern heap_t heap_pop(heap_t);
#define NEW_PQ_ELE(p, k) \
do { \
(p) = (typeof(p)) malloc(sizeof(*p)); \
((pq_node_t *) (p))->next = ((pq_node_t *) (p))->down = NULL; \
((pq_node_t *) (p))->key = (k); \
} while (0)
#define HEAP_PUSH(p, k, h) \
NEW_PQ_ELE(p, k); \
*(h) = heap_merge(((pq_node_t *) (p)), *(h))
</lang>
implementation:
<lang C>
#include <stdlib.h>
#include "pairheap.h"
static heap_t add_child(heap_t h, heap_t g) {
if (h->down != NULL)
g->next = h->down;
h->down = g;
}
heap_t heap_merge(heap_t a, heap_t b) {
if (a == NULL) return b;
if (b == NULL) return a;
if (a->key < b->key) {
add_child(a, b);
return a;
} else {
add_child(b, a);
return b;
}
}
/* NOTE: caller should have pointer to top of heap, since otherwise it won't
* be reclaimed. (we do not free the top.)
*/
heap_t two_pass_merge(heap_t h) {
if (h == NULL || h->next == NULL)
return h;
else {
pq_node_t
*a = h,
*b = h->next,
*rest = b->next;
a->next = b->next = NULL;
return heap_merge(heap_merge(a, b), two_pass_merge(rest));
}
}
heap_t heap_pop(heap_t h) {
return two_pass_merge(h->down);
}
</lang>
usage:
<lang C>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "pairheap.h"
struct task {
pq_node_t hd;
char task[40];
};
void main() {
heap_t heap = NULL;
struct task *new;
HEAP_PUSH(new, 3, &heap);
strcpy(new->task, "Clear drains.");
HEAP_PUSH(new, 4, &heap);
strcpy(new->task, "Feed cat.");
HEAP_PUSH(new, 5, &heap);
strcpy(new->task, "Make tea.");
HEAP_PUSH(new, 1, &heap);
strcpy(new->task, "Solve RC tasks.");
HEAP_PUSH(new, 2, &heap);
strcpy(new->task, "Tax return.");
while (heap != NULL) {
struct task *top = (struct task *) heap;
printf("%s\n", top->task);
heap = heap_pop(heap);
free(top);
}
}
</lang>
{{Out}}
<pre>
Solve RC tasks.
Tax return.
Clear drains.
Feed cat.
Make tea.
</pre>
=={{header|C sharp}}==
| |||