# ねじれヒープを利用した優先度付きキューをCで

グラフ上でダイクストラをするのをJavaで書くとすでに優先度付きキューが提供されているので多少楽はできるのですが、Cで書きたい場面もあるのです。
そこで、Cでも優先度付きキューをつかいたいです。優先度付きキューのインターフェイスを提供するなら

```#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define VAL_TYPE int

struct fork {
VAL_TYPE val;

struct fork *left;
struct fork *right;
};

bool is_empty(struct fork*);
VAL_TYPE min_elem(struct fork*);
struct fork* delete_elem(struct fork*);
struct fork* insert(VAL_TYPE, struct fork*);
struct fork* merge(struct fork*, struct fork*);
struct fork* join(struct fork*, struct fork*);
void freeHeap(struct fork*);
void showHeap(struct fork*);

int main()
{
struct fork *root = NULL;
int i;
for(i = 1; i < 10; i++) {
root = insert(i, root);
}
showHeap(root);
putchar('\n');

//Getting Value from heap
do {
printf("%d\n",min_elem(root));
root = delete_elem(root);
} while(!is_empty(root));

freeHeap(root);

return 0;
}

bool is_empty(struct fork *x)
{
if(x == NULL) {
return true;
} else {
return false;
}
}

VAL_TYPE min_elem(struct fork *x)
{
return x->val;
}

struct fork* delete_elem(struct fork *f)
{
struct fork *head, *a, *b;
head = f;
a = head->left;
b = head->right;

head->left = NULL;
head->right = NULL;
free(head);

return merge(a, b);
}

struct fork* insert(VAL_TYPE x, struct fork *a)
{
struct fork *new_fork;
if((new_fork = (struct fork*)malloc(sizeof(struct fork))) == NULL) {
fprintf(stderr, "Failed to allocate new fork for %d\n", x);
return NULL;
}
new_fork->val = x;
new_fork->left = NULL;
new_fork->right = NULL;

return merge(new_fork, a);
}

struct fork* merge(struct fork *a, struct fork *b)
{
if(b == NULL)
return a;
else if(a == NULL)
return b;
else
if(min_elem(a) <= min_elem(b))
return join(a, b);
else
return join(b, a);
}

struct fork* join(struct fork *a, struct fork *b)
{
struct fork *new_fork;
if((new_fork = (struct fork*)malloc(sizeof(struct fork))) == NULL) {
fprintf(stderr, "Failed to Allocate new fork\n");
return NULL;
}

new_fork->val = a->val;
new_fork->left = a->right;
new_fork->right = merge(a->left, b);

return new_fork;
}

void freeHeap(struct fork *root)
{
if(is_empty(root))
return;
if(!is_empty(root->left))
freeHeap(root->left);
if(!is_empty(root->right))
freeHeap(root->right);
free(root);
}

void showHeap(struct fork *root)
{
if(is_empty(root))
printf("nil ");
else {
printf("( ");
printf("%d ", root->val);
showHeap(root->left);
showHeap(root->right);
printf(") ");
}
}
```

ほぼそのままの実装になっています。

```\$ ./a.out
( 1 ( 2 ( 6 nil nil ) ( 4 nil ( 8 nil nil ) ) ) ( 3 ( 7 nil nil ) ( 5 nil ( 9 nil nil ) ) ) )
1
2
3
4
5
6
7
8
9
```

このような感じでちゃんとソートされて取りだせます。