frank-liu

浏览: 1682345 次
性别:
来自: 北京

最近访客更多访客>>

oneone1995

loginboot

45587123

liuqu11

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

求第二小数字所引出的讨论

博客分类：

java
data structures
algorithms

简介

我们在讨论求一个数组中最小的元素时，相对来说很简单，也很容易找到一个高效率的办法。在一些特殊的情况下甚至还可能有更加优化的方法。如果再把这个问题再深入一点。比如说，我们要求第二小的元素，那么有没有足够高效率的方法呢？

问题描述

在我们思考这个问题的时候，书上的有一个问题就是要求我们来验证在n个元素里，在最坏情况下找到第二小的元素需要经过n + lgn - 2次的比较。那么，我们能不能找到这么一种办法呢？先理一下大致的思路。

解决思路

遍历两次

这种办法相对比较简单直接，就是第一次遍历找到最小的元素。然后在剩下的集合里找最小的那个。这样就找到了第二小的。这种方法在最坏情况下的具体比较次数是n - 1 + n - 2 = 2n -3。很显然，虽然这是一个可以达到O(n)级别的方法。但是如果以问题中n + lgn - 2的标准来衡量的话，还是不够的。这种方法的实现代码如下：

public static int findSec(int[] a, int size)
{
	int smallest = 0, second = 1;
	for(int i = 1; i < size; i++)
	{
		if(a[i] < a[smallest])
			smallest = i;
	}
	swap(a, 0, smallest);
	for(int j = 2; j < size; j++)
	{
		if(a[j] < a[second])
			second = j;
	}

	return a[second];
}

public static void swap(int[] a, int i, int j)
{
	int temp = a[i];
	a[i] = a[j];
	a[j] = temp;
}

前面的办法是用了两个循环来遍历数组，我们也可以通过一次遍历来实现：

public static int findSecond(int[] a, int size)
{
	int first = 0, second = 0;
	if(size > 1)
	{
		if(a[0] < a[1])
			second = 1;
		else
			first = 1;
	}

	for(int i = 2; i < size; i++)
	{
		if(a[i] < a[second])
		{
			if(a[i] < a[first])
			{
				second = first;
				first = i;
			}
			else
				second = i;
		}
	}

	return a[second];
}

虽然我们能实现达到O(n) 这个量级的方法，但是和前面的要求来说，还是没达到。很显然，第一种办法没法解决。

从堆排序里借鉴的思路

我们前面如果看过堆排序就知道它是一个数组，但是用一种完全二叉树的角度来操作它。比如说我们有一个数组[16, 14, 10, 8, 7, 9, 3, 2, 4, 1]。那么，按照堆排序的思路，它对应的二叉树关系如下图：

这部分的特性对于我们构造调整的结构有什么帮助呢？毕竟这里是在一个已经有的数组中间来构造。但是这里有一个比较有意思的性质，对于我们后面的分析有帮助。假设有一棵完全的二叉树，它的叶结点层也是完全覆盖的，那么这一层的叶结点数目必然为2**k(2的k次方)。从叶结点往上的结点每次都为它的一半，直到根结点。那么，从根结点到叶结点上面一层的所有结点数目正好构成一个等比数列，他们的总数为2**k - 1。也就是说比叶结点数目小1。这给了我们一个提示。就是假设我们有一组元素作为叶结点，然后在它的基础上来构造完全二叉树的上层部分，比如说构造成一个最小堆，那么这部分的花费如果有办法控制的话，有希望实现通过n-1次的比较得到一个这样的最小堆。那么我们看如下的一种构造树的方式：

在这里，假设我们有数组[1, 2, 3, 4] 作为叶结点一层。然后每次两个两个的比较，将较小的那个取出来作为上面一层的结点。那么，在一个理想的情况下，我们假设叶结点总共有2**k个。这次比较生成它上一层的叶结点需要的比较次数为2**(k-1)，也就是说为叶结点数字的一半。再往上一层构造的比较则在原来的基础上再减半。和前面的比较类似，前面所有的比较次数正好构造成一个等比数列，从1到2**(k-1)，那么他们的和就刚好为2**k - 1。经过这一番推导，我们发现通过这么构造一番的方式是可以实现在n - 1次的比较来构造出一个最小堆的。而这个最小堆的构造方式和堆排序的情况不一样。更确切的来说，这个堆有一个明确的说法。它就是胜者树。

后面我们会详细分析胜者树。那么好吧，按照我们原来的要求，是要求实现最后得到第二小的元素，而且比较次数为n + lgn - 2。我们这里只是通过n - 1次比较得到了最小的元素。怎么来找到这个第二小的元素呢？这里又利用到了胜者树一个有意思的地方。我们看前面的图。最终站在顶上的元素是最小的元素。他们所有的比较过程相当于是一个竞赛的淘汰过程。所有参加竞赛的队伍捉对厮杀，然后淘汰到只剩下最后一个。该到哪里找这个第二的呢？这个和具体的比赛不一样。具体的比赛肯定是决赛里头赢的那个第一，输的那个第二。这里头就好像所有pk的怪物都给设定了武力值，武力高的那个赢武力低的那个。可是如果一开始那个武力第二的就和第一的分到一起呢？那么这个老二就很悲催的第一轮被灭了。既然是老二嘛，肯定火力还是比较威猛，也可能一开始没碰到呢？那么他们也可能在中间的某一个阶段碰到，或者在最后的决赛阶段给碰上。总之，最后的冠军已经定下来的情况下，它必然要和这么个老大碰面的。换一个角度来说，我们可以说，它必然会和这么个老大会一面，成为老大夺冠路上的一个冤魂。这样，如果我们要找这个第二小的元素，只要找这个最小元素它曾经比较过的对象就知道了。而我们得到的胜者树可是一路记录了最小元素从小组赛一直pk到决赛的记录的。我们从前面的图中可以看到，只要顺着根结点向下，只要沿着和根结点值一样的结点遍历，那么对应的另外一个结点就是和它pk过的对手。而那个第二小的元素就在它所有pk过的对手里面。

我们看到，我们构造的树是一棵完全二叉树，那么树的高度为lgn。从根结点开始向下走到叶结点进行比较，实际的比较次数为lgn - 1。到这里，我们的思路就完全理清楚了。原来，找这么个老二就是这么一个过程：1. 构造一棵胜者树，这样就可以找到最小的元素。 2. 从根结点开始向下比较每个和它值不同的子结点，然后找到第二小的元素。他们总共的比较次数为n + lgn - 2。

胜者树

前面是通过一个简单的讨论引出了胜者树。我们来看一个更一般化的胜者树的样子：

胜者树一个更正式的定义是通过锦标赛思想来建立的树，它的每个非终端结点存储的是左右子结点中的优胜者。胜者树实质上是对n个记录的关键字进行两两比较，得到个优胜者，作为第一步比较的结果保留下来。然后这个较小(大)者之间再进行两两比较，…，如此重复，直到选择出最小关键字的记录为止。现在，我们再来看看具体胜者树的构造。

构造

我们前面构思的一个思路是一种比较理想的状态，要求我们的叶结点个数也就是元素的个数为2**k，实际中元素的个数很可能不是正好这么多。那么，按照我们前面堆排序的构造和分析，我们必须要构造这么一个完全的二叉树。我们可以采用两种方式，一种就是将原来的元素补齐，补到刚好大于它数字的2**k个。然后再来构造。还有一种就是我不需要叶结点有2**k个，只要保证从叶结点往上的层正好符合2**k个的标准也可以。就像堆排序构造的堆一样，叶结点不一定是满的，但是上面的结点肯定都是满的。相对来说，第二种方式需要用到的额外空间少一点。我们就以第二种方法为例来讨论。

假定有n个元素，我们总共这棵树需要多少个结点呢？从前面的分析可以得到，需要的元素数目为2**k - 1 + n个。其中2**k为假设叶结点是满的，它所有叶结点的数目。为什么是这么多个呢？我们这里就不再详细推导，只要记住一点，对于一个叶结点是满的二叉树，假设叶结点数目为2**k个，那么它上面其他所有结点的总和为2**k -1，也就是说比满的叶结点数目少一个。

还有一个问题就是，我们是从叶结点向根结点来推导，这n个元素应该放在这个新数组的最后。这部分初始化的代码可以实现如下：

public void buildTree(int[] t)
{
	int length;
	for(length = 2; length < t.length; length *= 2);
	treeLength = length - 1 + t.length;
	a = new int[treeLength];
	for(int i = 0; i < t.length; i++)
		a[length - 1 + i] = t[i];
	for(int j = 0; j < length -1; j++)
		a[j] = Integer.MAX_VALUE;
	build(length - 1, treeLength - 1);
}

因为这里要比较数值的大小，我们从前面的图里可以看到，有一些上层空缺的位置需要补对应的数值来满足整个满二叉树的结构又不能破坏胜者树的结果，所以我们首先将非n个元素之前的结点值都置成Integer.MAX_VALUE。这里的build方法则是构造的详细步骤，其代码实现如下：

public void build(int start, int end)
{
	while(start != end)
	{
		for(int k = start; k <= end; k += 2)
		{
			if(k + 1 <= end)
				a[parent(k)] = a[k] > a[k + 1] ? a[k + 1] : a[k];
			else
				a[parent(k)] = a[k];
		}
		start = parent(start);
		end = parent(end);
	}
}


public int parent(int i)
{
	if(i % 2 == 0)
		return i / 2 - 1;
	else
		return i / 2;
}

在build方法里，每次我们取这一层结点的最左边一个结点和最右边的结点，在遍历的过程中两两比较，将较小的那个设为相邻两个结点的父结点。一直遍历到根结点。

查找

查找的基本过程如下：1. 从根结点开始，看它的左右子结点，如果一个结点和根结点值相同，则取另外一个结点的值作为第二小结点的比较值。2. 进入和根结点值相同的这个子结点，重复步骤1。这个整体过程虽然表述起来比较简单，其实现还是有不少诡异的地方：

public int findSecondMin()
{
	int secondMin = Integer.MAX_VALUE;
	int i = 0;
	while(left(i) < treeLength || right(i) < treeLength)
	{
		if(left(i) < treeLength && a[left(i)] == a[0])
		{
			if(right(i) < treeLength && a[right(i)] < secondMin)
			{
				secondMin = a[right(i)];
			}
			i = left(i);
		}
		else if(right(i) < treeLength && a[right(i)] == a[0])
		{
			if(left(i) < treeLength && a[left(i)] < secondMin)
			{
				secondMin = a[left(i)];
			}
			i = right(i);
		}
	}
	return secondMin;
}

public int left(int i)
{
	return 2 * i + 1;
}

public int right(int i)
{
	return 2 * i + 2;
}

这部分的代码就不再详细解释了。有了前面的分析应该也很容易理解。

调整

这一部分是后面新增加的内容。我们在某些情况下，纯粹出于对胜者树的性质的一个维护。如果我们修改了叶结点的一个值，就有可能引起一个连锁的变化。我们看如下的一个示例：

这是按照我们前面的讨论构造的一棵胜者树。如果我们将叶结点1的值修改为4，那么，为了保证树的性质，我们需要做一些如下的修改：

这个过程在于，在原来结点被修改的地方，我们需要重新进行比较和调整，一直向上回溯到根结点。每次需要和它的兄弟结点进行比较。

具体实现的代码如下：

public void adjust(int i, int val)
{
	a[i] = val;
	while(parent(i) >= 0)
	{
		if(i % 2 == 0 && i - 1 >= 0)
		{
			a[parent(i)] = a[i] > a[i - 1] ? a[i - 1] : a[i];
		}
		else if(i % 2 == 1 && i + 1 <= treeLength)
		{
			a[parent(i)] = a[i] > a[i + 1] ? a[i + 1] : a[i];
		}
		i = parent(i);
	}
}

这里有一个判断i % 2的地方，是用于判断当前结点的下标值是否为奇数或者偶数。因为胜者树本身的满二叉树属性。所有在左子结点的元素下标值为奇数，右结点的元素下标值为偶数。

总结

这里是根据一个求第二小的数进行的推导。为了找到一个可以更加优化的思路居然要折腾这么多。可见，这些问题背后的思想还是很丰富的。除了胜者树，其实还有类似的数据结构败者树。他们的思想也很类似。在一些更通用的问题比如求最小的若干个数时，还有一些其他的方法和思路，不过和堆也有很强的联系。胜者树，败者树他们和堆排序，求最小（大）的k个元素的问题以及多路归并排序等外排序的算法也有很强的关系。在后续的一些文章中也会针对这几个点八卦八卦。