标题:
二项队列分析及实现
[打印本页]
作者:
yuyang911220
时间:
2016-8-20 20:27
标题:
二项队列分析及实现
一，介绍
什么是二项队列，为什么会用到二项队列？
与二叉堆一样，二项队列也是优先级队列的一种实现方式。在
数据结构--堆的实现之深入分析 的末尾
，简单地比较了一下二叉堆与二项队列。
对于二项队列而言，它可以弥补二叉堆的不足:merge操作的时间复杂度为O(N)。二项队列的merge操作的最坏时间复杂度为O(logN)。
二项队列的合并操作为什么是O(logN)？因为：对于N个结点的二项队列，最多只有logN棵二项树。而合并操作就是合并两棵高度相同的二项树。（合并操作是指将二个
二项队列
合并，合并这两个二项队列中
高度相同
的二项树）
二，二项队列的基本操作及实现
在详细介绍二项的队列的基本操作之前，先了解下二项队列这种数据结构：
1）一个二项队列是若干棵树的集合。也就是说，二项队列不仅仅是一棵树，而是多棵树，并且每一棵树都遵守堆序的性质，所谓堆序的性质，就是指每个结点都比它的左右子树中结点要小（小顶堆）。这棵树称为“二项树”
2）二项队列中的树高度不同，一个高度至多存在一棵二项树。将高度为0的二项树记为 B(0)，高度为 k 的二项树记为 B(k)
也就是说，对于k>=0，二项队列中至多存在一棵 B(k)的二项树。
3）B(k)是由 B(0)、B(1)、B(2)....B(k-1)组成的。B(0)是一棵单节点(2^0 = 1)的树，B(k)中含有 2^k 个结点。
高度为 k 的二项树B(k)通过将一棵二项树B(k-1)附到另一棵二项树B(k-1)的根上构成。而B(k-1)又可以由B(k-2)附到另一棵B(k-2)的二项树上，故正如上面提到，B(k)是由 B(0)、B(1)、B(2)....B(k-1)组成的。
4）具有N个结点的二项队列
最多
有 logN 棵二项树。因为，每棵二项树B(k)中含有2^k个结点。
故：2^0 + 2^1 + 2^2 + .... + 2^k = N，得到 k=logN。k为树的棵数。
注意到上面提到的是“最多” 有logN 棵二项树，这说明一个二项队列可以缺少某棵 B(i) , 0<=i<=k
5）由二项树中结点个数的性质(B(k)有2^k个结点)，而二项队列又是若干二项树的集合，故二项队列可以采用
二进制数
来标记：
如，大小为13(共有13个结点)的二项队列可以用森林 B(3)、B(2)、B(0)表示，并可以把这种表示写成 1101，1101以二进制形式表示13，而且还表示了该二项队列中，不存在B(1)这样的树。
介绍了二项队列的性质或者说逻辑结构，现在介绍下二项队列的存储结构。
二项队列是在内在中如何存储的呢？（从网上找到一张图如下：）
首先是需要一个一维数组。该数组中的每个元素存储一棵二项树的根结点指针。比如，最右边的那个数组元素存储了一颗高度为0的二项树B(0)。B(0)只有一个结点，该结点的权值为13。如果数组的长度表示二进制的位数，那么这个二项队列表示为 00001101
这说明该二项队列不存在高度为7、6、5、4、1 这样的二项树：B(7)、B(６)、B(５)、B(４)、B(1)
此外，还可以看出：
①
数组大小为二项树的数目乘2加1，或者说二项树的数目是数组的长度除以2再减去1。二项树在数组中存储是按高度排序的。
②数组第 i 号索引处，存储的是高度为 i 的二项树。如，第0号索引，存储高度为0的二项树，该二项树只有一个结点，结点权值为13
除了需要一维数组存储各棵树的根结点外，当然还需要保存各棵二项树了，二项树的采用的是链表 表示，这里采用的是“左孩子右兄弟”表示法。
因此，二项队列的实现类的结构如下：
[url=]
[/url]
1
public
final
class
BinomialQueue<AnyType
extends
Comparable<?
super
AnyType>>
2
{
3
4
private
static
final
int
DEFAULT_TREES = 1
;
5
6
private
int
currentSize;
//
# items in priority queue
7
private
BinNode<AnyType> [ ] theTrees;
//
An array of tree roots
8
9
/**
10
* Construct the binomial queue.
11
*/
12
public
BinomialQueue( )
13
{
14
theTrees =
new
BinNode[ DEFAULT_TREES ];
15
makeEmpty( );
16
}
17
18
19
private
static
class
BinNode<AnyType>
20
{
21
AnyType element;
//
The data in the node
22
BinNode<AnyType> leftChild;
//
Left child
23
BinNode<AnyType> nextSibling;
//
Right child
24
//
Constructors
25
BinNode( AnyType theElement )
26
{
27
this
( theElement,
null
,
null
);
28
}
29
30
//
other operations.....
31
}
32
//
other operations.....
33
}[url=]
[/url]
第7行是一维数组，第19至23行是采用“左孩子右兄弟”表示法的结点的定义。
①merge操作
merge操作是合并二个二项队列，合并二项队列过程中需要合并这两个二项队列中 高度相同的二项树(后面的combineTrees()方法)
假设需要合并二项队列H(1)和H(2)，合并后的结果为H(3)。合并两个二项队列的过程如下：
a)寻找H(1)和H(2)中高度相同的二项树，调用combineTrees()合并这两颗二项树
b)重复 a) 直至树中不再有高度相同的二项树为止
代码分析如下：
[url=]
[/url]
1
/**
2
* Return the result of merging equal-sized t1 and t2.
3
*/
4
private
BinNode<AnyType> combineTrees( BinNode<AnyType> t1, BinNode<AnyType>
t2 )
5
{
6
if
( t1.element.compareTo( t2.element ) > 0
)
7
return
combineTrees( t2, t1 );//第一个参数t1总是代表：根的权值较小的那颗二项树
8
t2.nextSibling =
t1.leftChild;//把权值大的二项树的左孩子作为权值小的二项树的右兄弟
9
t1.leftChild =
t2;//把权值小的二项树 作为 权值大的 二项树 的 左孩子
10
return
t1;
11
}[url=]
[/url]
combineTrees()方法用来合并两棵高度相同的二项树，(注意是二项树，而不是二项队列)。树采用的是左孩子右兄弟表示法。
第4行，t1是根的权值较小的二项树树，第8-9行，
将根权值较大的那颗二项树成为根权值较小的二项树(t1)的子树
，即可完成二项树的合并。
欢迎光临 电子技术论坛_中国专业的电子工程师学习交流社区-中电网技术论坛 (http://bbs.eccn.com/)
Powered by Discuz! 7.0.0
[/url][/url][/url][/url]