左式堆的建立及其基本操作

左式堆较最小堆而言，可以合并两个左式堆。

#include <stdio.h>

#include<stdlib.h>


typedef int ElementType;
struct TreeNode;
typedef struct TreeNode *PriorityQueue;


PriorityQueue Initialize(ElementType X);                         //初始化X
ElementType FindMin(PriorityQueue H);                           //查找最小值
int IsEmpty(PriorityQueue H);                                   //判空
PriorityQueue Merge(PriorityQueue H1,PriorityQueue H2);         //合并
static PriorityQueue Merge1(PriorityQueue H1,PriorityQueue H2);


#define Insert(X,H)  (H = Insert1((X),H));
PriorityQueue Insert1(ElementType X,PriorityQueue H);


#define DeleteMin(H)    (H = DeleteMin1(H));
PriorityQueue DeleteMin1(PriorityQueue H);                      //删除最小值
void  SwapChildren(PriorityQueue H);                            //交换
int main(void)
{
PriorityQueue H;


H = Initialize(99);


Insert(45,H);
Insert(44,H);
Insert(12,H);
Insert(6,H);


DeleteMin(H);
DeleteMin(H);

printf("%d",FindMin(H));


printf("\nHello World!\n");
return 0;
}


struct TreeNode
{
ElementType Element;
PriorityQueue Left;
PriorityQueue Right;
int Npl;
};


PriorityQueue Merge(PriorityQueue H1, PriorityQueue H2)                 //合并1
{
if(NULL == H1)
return H2;
if(NULL == H2)
return H1;
if(H1->Element < H2->Element)
return Merge1(H1,H2);
else
return Merge1(H2,H1);
}


static PriorityQueue Merge1(PriorityQueue H1, PriorityQueue H2)         //合并2
{
if(NULL == H1->Left )
H1->Left = H2;
else
{
H1->Right = Merge(H1->Right,H2);
if(H1->Left->Npl < H1->Right->Npl)
SwapChildren(H1);
H1->Npl = H1->Right->Npl + 1;
}


return H1;
}


PriorityQueue Insert1(ElementType X, PriorityQueue H)    //插入一个X，实际上就是与一个节点合并
{
PriorityQueue SingleNode;
SingleNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
if(NULL == SingleNode)
printf("Out Of Space\n");
else
{
SingleNode->Element = X;
SingleNode->Npl = 0;
SingleNode->Left = SingleNode->Right = NULL;
H = Merge(SingleNode,H);
}


return H;
}


PriorityQueue DeleteMin1(PriorityQueue H) //删除最小值
{
PriorityQueue LeftHeap,RightHeap;
if(IsEmpty(H))
{
printf("Priority Is Empty\n");
return H;
}


LeftHeap = H->Left;
RightHeap = H->Right;
free(H);


return Merge(LeftHeap,RightHeap);
}




void  SwapChildren(PriorityQueue H) //交换左右儿子
{
PriorityQueue P;
P = H->Left;
H->Left = H->Right;
H->Right = P;
}


PriorityQueue Initialize(ElementType X) //初始化X,
{
PriorityQueue H;
H = (struct TreeNode*)malloc(sizeof(struct TreeNode));
H->Left = H->Right = NULL;
H->Element = X;
H->Npl = 0;


return H;
}


ElementType FindMin(PriorityQueue H) //返回最小值，即第一个元素
{
if(IsEmpty(H))
return -1;
else
return H->Element;
}


int IsEmpty(PriorityQueue H) //判空
{
return H == NULL;
}