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

グラフ上でダイクストラをするのをJavaで書くとすでに優先度付きキューが提供されているので多少楽はできるのですが、Cで書きたい場面もあるのです。
そこで、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

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