高度优先左高树的实现

目的：为了更好的支持堆之间的合并

定义shortest(x)为从x到一个外部节点的最短路径

左高树：是一颗二叉树，如果该二叉树不为空，则对于其中的每个节点x，都有shortest(left_child(x))>=shortest(right_child(x))

以下实现的是最小左高树的合并，插入，删除最小值:

插入可以看成一颗左高树和一颗只有一个节点的左高树的合并

删除最小值可以看成该值所对应的左树和右树的合并

/*

* 2008/07/08 By YaoJianming

*/

#include
#include

struct element {
        int key;
};
struct leftist {
        element data;
        leftist *left_child;
        leftist *right_child;
        int shortest;
};

void swap(leftist *&a, leftist *&b)
{
        leftist *temp = a;
        a = b;
        b = temp;
}

void min_union(leftist *&a, leftist *&b)
{
        if(a->data.key > b->data.key) {
                swap(a, b);
        }
        if(a->right_child == NULL) {
                a->right_child = b;
        } else {
                min_union(a->right_child, b);
        }
        if(a->left_child == NULL) {
                a->left_child = a->right_child;
                a->right_child = NULL;
        } else if(a->left_child->shortest < a->right_child->shortest) {
                swap(a->left_child, a->right_child);
        }
        a->shortest = (a->right_child == NULL) ? 1: a->right_child->shortest + 1;
}

void min_combine(leftist *&a, leftist *&b)
{
        if(a == NULL)
                a = b;
        else if(b != NULL) {
                min_union(a, b);
                b = NULL;
        }
}

void insert(leftist *&a, leftist *&b)
{
        min_combine(a, b);
}

element del_min(leftist *&a)
{
        element temp = a->data;
        min_combine(a->left_child, a->right_child);
        a = a->left_child;
        return temp;
}

#define maxsize 100
struct queue {
        leftist *queue[maxsize];
        int front;
        int rear;
};

void initqueue(queue *q)
{
        q->front = 0;
        q->rear = 0;
}

void addqueue(queue *q, leftist *root)
{
        if((q->rear+1)%maxsize == q->front) {
                printf("queue full\n");
                exit(1);
        }
        q->queue[q->rear] = root;
        q->rear = (q->rear+1)%maxsize;
}

void delqueue(queue *q, leftist *&root)
{
        if(q->front == q->rear) {
                printf("queue empty\n");
                exit(1);
        }
        root = q->queue[q->front];
        q->front = (q->front+1)%maxsize;
}

void level(leftist *a)
{
        queue q;
        initqueue(&q);
        addqueue(&q, a);
        while(q.front != q.rear) {
                delqueue(&q, a);
                printf("%d ", a->data.key);
                if(a->left_child != NULL) addqueue(&q, a->left_child);
                if(a->right_child != NULL) addqueue(&q, a->right_child);
        }
}

int main()
{
        leftist *a = NULL;
        for(int i=1; i<10; ++i) {
                leftist *p = new leftist;
                p->left_child = p->right_child = NULL;
                p->shortest = 1;
                p->data.key = i;
                insert(a, p);
        }
        del_min(a);
        level(a);
        printf("\n");
}