脱线MIN问题及源代码——Union-Find算法的应用与推广

脱线MIN问题：

指令Insert(i)：把元素i插入集合s中。

指令Extract_min：从集合S中找出最小元并进行删除。

两种指令的简单表示法：用i表示Insert(i)，用E表示Extract_min。

例：7，2，5，9，E，6，E，E，3，E，1，4，E

这种序列满足两个性质：

1） 任一i （1<=i<=n）在序列中最多出现一次（元素之间互不相同）；

2）从左起任意一段中，插入指令条数大于等于E指令条数。（否则无元素可删。）

算法结果：

给定一个Insert与Extract_min的指令序列之后，对在序列中出现的每个i，算法要输出i是被第几条E指令删除的（对于序列中未出现的i，算法应输出相应信息。）

上例中有：1(5), 2(1), 3(4), 4(未被删除)，5(2)，6(3)，7，9与4一样未被删除，8未出现。

脱线MIN算法思路：

算法开始之前，先把所有元素的所属集合名NAME[i]置为0（O(n)）；再扫描指令序列，把由E隔开的每段中的元素组成若干个集合并命名（O(n)）：

e.g.: 1={2,5,7,9}，2={6}，3=null，4={3}，5={1,4}，6=null

用集合名（数字）来表示删除i的E指令序号。

算法从i=1开始逐一检查，找到1所在的元素集合名（5），输出1是被第5条E指令删除的;

输出后用UNION算法把集合5与其后的集合6合并为6：6={1,4}。

下一步看i=2，找到2所在的元素集合名（1），输出2是被第1条E指令删除的;

输出后用UNION算法把集合1与其后的2合并,得到2={2,5,6,7,9}。

其次看i=3，找到3所在的元素集合名（4），输出3是被第4条E指令删除的；

输出后用UNION算法把集合4与其后的集合6合并（此时集合5已经不存在了），得到6={1,3,4}。

i=4时，找到4所在的元素集合名（6），但6>E指令条数（只有5条），故输出“4未被删除”。

i=5时，找到5所在的元素集合名（2），输出5是被第2条E指令删除的；

输出后用UNION算法把集合2与其后的集合3合并，得3={2,5,6,7,9}。

i=6时，找到6所在的元素集合名（3），输出6是被第3条E指令删除的；

输出后用UNION算法把集合3与6合并，得6={1,2,3,4,5,6,7,9}其后的7，9执行Find后均得6，故与4一样未被删除，而8未在序列中出现，因Find(8)=0，故应输出“8未出现”。

为合并时方便地找到后继集合，引入Pred和Succ 2个数组：

Pred[j]记录了前一个集合的名称（数字），初始时为j-1，

Succ[j]记录了后一个集合的名称（数字），初始时为j+1。

 

 

在Union-Find树结构的基础上，解决了脱线MIN问题。考虑了路径压缩。

测试数据：7，2，5，9，E，6，E，E，3，E，1，4，E

运行截图：

输入：

 

输出：

算法：

for i=1 to n do

{

   j←Find(i); /*找到i所属集合名(数字)即删除i的E指令序号*/

   if j=0 then {输出“i未在序列中出现”}

   else if j>k then

    {输出“i未被删除”}

   else    /* i确实被删除了*/

    {

      输出“i是被第j条E指令所删除”；

      UNION(j，Succ[j]，Succ[j])；

      Succ[Pred[j]]←Succ[j]；/* 集合j不再存在*/

       Pred[Succ[j]]←Pred[j]

    }

}

 

 

算法的主要工作是执行O(n)条Find指令，（其余工作在循环的每一轮都是常数时间）故该算法的时间复杂度为O(n*G(n))。

因要对合并后的集合（树结构）进行强制命名，故采用可强制命名为k的UNION(i,j,k)算法：

 

• 数组元素ROOT[i]中存放集合名为i的根结点编号；
• 数组元素COUNT[t]中存放编号t的结点为根的子树中的结点个数；
• 数组元素FATHER [t]中存放编号t的结点的父结点编号；
• 数组元素NAME[t]中存放t结点为根的树所对应的集合名。

 

wlg assume COUNT[ROOT[i]]<=COUNT[ROOT[j]]

  (otherwise interchange i and j in the following lines)

LARGE←ROOT[j];

SMALL←ROOT[i];

FATHER[SMALL]←LARGE;

COUNT[LARGE]←COUNT[LARGE]+ COUNT[SMALL];

NAME[LARGE]←k;

ROOT[k]←LARGE

由于该算法不执行Find，故在O(1)时间里即可完成。

 #include <stdio.h>

#include <malloc.h>
#define NUM 10
typedef struct Node//节点
{
	int name;//集合名
	int value;//value,和index数值相同
	int father;//父亲节点
	int rank;//秩
}TreeNode, *BiTree;
typedef struct Sets//集合
{
	int num;//集合的根结点
	int pre;//前面的集合名
	int suc;//后面的集合名
	int used;
}SetNode, *BiSet;
BiTree bt;
BiSet bs;
//创建集合
void creatSet(int assetNum){
	if (assetNum>1)
	{
		bs[assetNum-1].suc=assetNum;
		bs[assetNum].pre=assetNum-1;
	}
	bs[assetNum].used=1;
}
//插入操作
void insert(int i,int assetNum){
	if (bs[assetNum].num == 0)
	{
		bt[i].rank=0;
		bt[i].name=assetNum;
		bs[assetNum].num=i;
	}else{
		bt[bs[assetNum].num].rank=1;
	};
	bt[i].father=bs[assetNum].num;
}
//删除最小操作
int extract_min(int assetNum){
	assetNum++;
	creatSet(assetNum);
	return assetNum;
}
//初始化，输入及构造数据结构
int initializeNode()//返回构造了几个集合树
{
	bs=(BiSet)malloc(NUM*sizeof(SetNode));
	bt=(BiTree)malloc(NUM*sizeof(TreeNode));
	for (int i=0;i<NUM;i++)
	{
		bt[i].name=0;
		bt[i].value=0;
		bt[i].rank=0;
		bt[i].father=0;
		bs[i].pre=0;
		bs[i].suc=0;
		bs[i].num=0;
		bt[i].value=i;
		bs[i].used=0;
	}
	int r=-2;
	int assetNum=1;
	creatSet(assetNum);
	while(r!=-1){
		printf("请输入一个不重复正数字，作为insert操作。或者输入0表示一个extract_min操作,-1表示退出输入");
		scanf("%d",&r);
		if (r>0)
		{
			insert(r,assetNum);
		}
		else if (r==0)
		{
			assetNum=extract_min(assetNum);
		}
	}
	//assetNum=extract_min(assetNum);
	return assetNum;
}
/************************************************************************
找到某个节点的根节点
输入参数：

输出参数：
	index：根结点节点编号
************************************************************************/
int find(int value){
	BiTree t=&bt[value];
	if (t->father!=value)
	{
		t->father=find(bt[bt[value].father].value);
	}
	return t->father;
}
//返回节点所在的集合
//即返回节点的根节点的name
int find_setNum(int value){
	int t=bt[find(value)].name;
	return t;
}
//输入一个集合名，将这个集合和它的下一个集合合并，并命名为下一个集合名
void funion(int setNum){
	int index1=bs[setNum].num;
	int suc=bs[setNum].suc;
	int index2=bs[suc].num;
	if (bt[index1].rank>bt[index2].rank)//当
	{
		bt[index2].father=index1;
		bs[suc].num=index1;
		bt[index1].name=suc;
	}
	else if (bt[index1].rank ==bt[index2].rank)
	{
		bt[index1].father=index2;
		bt[index2].rank++;
	}
	else{
		bt[index1].father=index2;
	}
	bs[setNum].used=0;
	int pre=bs[setNum].pre;
	bs[pre].suc=suc;
	bs[suc].pre=pre;

}
//处理。输出
void deal(int setsCount){
	for (int i=1;i<NUM;i++)
	{
		if (bt[i].father==0)
		{
			printf("%d没有出现在序列中\n",i);
		}
		else{
			int setsNum=find_setNum(i);
			if (setsNum == setsCount)
			{
				printf("%d没有被删除\n",i);
			}
			else if (setsNum <setsCount)
			{
				printf("%d节点被第%d条指令删除\n",i,setsNum);
				funion(setsNum);
			}
			else
				printf("err:根据节点查找到一个错误的集合名\n");
		}
	}
}
void main(){
	//初始化、输入及构造数据结构
	int setsCount=initializeNode();
	//处理
	deal(setsCount);
	//打印
	for (int i=0;i<NUM;i++)
	{
		printf("index/value:%d, ",i);
		printf("name:%d, ",bt[i].name);
		printf("rank:%d, ",bt[i].rank);
		printf("father:%d\n ",bt[i].father);
	}
	printf("asset[name]:index\n");
	for (int i=0;i<NUM;i++)
	{
		printf("set num:%d, ",i);
		printf("use:%d, ",bs[i].used);
		printf("num:%d, ",bs[i].num);
		printf("pre:%d, ",bs[i].pre);
		printf("suc:%d\n",bs[i].suc);
	}
	//等待显示
	printf("\nprint end");
	int i;
	scanf("%d",&i);
}