Priority queue: Difference between revisions
Content deleted Content added
SqrtNegInf (talk | contribs) m →{{header|Sidef}}: Fix link: Perl 6 --> Raku |
|||
Line 754: | Line 754: | ||
Feed cat |
Feed cat |
||
Make tea</pre> |
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}}== |
=={{header|C sharp}}== |