// erixiangduilie.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include<iostream>
using namespace std;

typedef struct BinNode *Position;
typedef struct Collection *BinQueue;
typedef struct BinNode *BinTree;
#define MaxSize 10
#define Capacity 200
#define Inf 65535
#define MaxTrees 10
struct BinNode
{
	int element;
	Position LeftChild;
	Position NextSibiliing;
};

struct Collection
{
	int CurrentSize;
	BinTree TheTrees[MaxSize];
};

BinTree CombineTrees(BinTree T1, BinTree T2)   //合并相同大小的树
{
	if (T1->element > T2->element)
		return CombineTrees(T2, T1);
	T2->NextSibiliing = T1->LeftChild;
	T1->LeftChild = T2;
	return T1;
}

BinQueue merge(BinQueue H1, BinQueue H2)
{
	BinTree T1, T2, Carry = NULL;                   //T1,T2为对应位置的树,Carry代表进位
	if (H1->CurrentSize + H2->CurrentSize > Capacity)
		cout << "Merge would exceed capacity";
	H1->CurrentSize += H2->CurrentSize;
	for (int i = 0, j = 1; j <= H1->CurrentSize; i++, j *= 2)   //i代表第几棵树，j用来结束循环，CurrentSize记录的是最后一棵树节点的数量
	{
		T1 = H1->TheTrees[i];                                  //各取出第i位的树
		T2 = H2->TheTrees[i];
		switch (!!T1 + 2 * !!T2 + 4 * !!Carry)               //！！用来把T1等的空和非空的状态变成数字量0，1，然后整个表达式变成二进制000，1代表该元素存在，0代表该元素不存在
		{
		   case 0:  //没树
		   case 1:  //只有H1
			   break;
		   case 2:    //只有H2
			   H1->TheTrees[i] = T2;
			   H2->TheTrees[i] = NULL;
			   break;
		   case 4:    //只有Carry,case 4要在case 3前？
			   H1->TheTrees[i] = Carry;
			   Carry = NULL;
			   break;
		   case 3:    //有H1，H2
			   Carry = CombineTrees(T1, T2);
			   H1->TheTrees[i] = H2->TheTrees[i] = NULL;
			   break;
		   case 5:  //H1和Carry
			   Carry = CombineTrees(T1, Carry);
			   H1->TheTrees[i] = NULL;
			   break;
		   case 6:  //H2和Carry
			   Carry = CombineTrees(T2, Carry);
			   H2->TheTrees[i] = NULL;
			   break;
		   case 7:  //三者都有，则留一个在i位，剩下合并
			   H1->TheTrees[i] = Carry;
			   Carry = CombineTrees(T1, T2);
			   H2->TheTrees[i] = NULL;
			   break;
		}
	}
	return H1;
}
BinQueue Initialize();                         //初始化二项队列函数，只写声明，未写实现
int deleteMin(BinQueue H)
{
	int MinTree;           //用来记录最小根所在的位置
	BinQueue DeleteQueue;
	Position DeleteTree, OldRoot;
	int MinItem;

	if (H == NULL)
	{
		cout << "Empty!";
		return -Inf;
	}

	MinItem = Inf;
	for (int i = 0; i < MaxTrees; i++)   //查找最小的树根
	{
		if (H->TheTrees[i] && H->TheTrees[i]->element < MinItem)
		{
			MinItem = H->TheTrees[i]->element;
			MinTree = i;
		}
	}

	DeleteTree = H->TheTrees[MinTree];
	OldRoot = DeleteTree;
	DeleteTree = DeleteTree->LeftChild;
	free(OldRoot);     //这里用来释放最小值节点的地址，不能直接直接释放DeleteTree，会丢掉信息。

	DeleteQueue = Initialize();
	DeleteQueue->CurrentSize = (1 << MinTree) - 1;    //不懂

	for (int j = MinTree - 1; j >= 0; j--) //此循环把一颗去掉根的树得到的很多子树分别装入一个新的二项队列
	{
		DeleteQueue->TheTrees[j] = DeleteTree;
		DeleteTree = DeleteTree->NextSibiliing;
		DeleteQueue->TheTrees[j]->NextSibiliing = NULL;
	}

	H->TheTrees[MinTree] = NULL;
	H->CurrentSize -= DeleteQueue->CurrentSize + 1;

	merge(H, DeleteQueue);
	return MinItem;
}

int main()
{
    return 0;
}