胜者树败者树

2010-06-01 01:05:04

标签：

胜者树则是常见的归并完全二叉树形式。

题：给定一个数组array，长度为16。如何采用最少的比较次数找出第二大的元素？

1. 直观方法是通过两次冒泡排序，15+14=29 次比较可找到第二大的元素。然而直观方法显然没有应用到一些已经比较过的信息。

2. 采用归并排序，构造胜者树。与该胜者比较过的元素有4个，只需要对这些元素进行比较即可，共比较次数15（胜者树）+ （4-1）=18 次比较。

 

败者树在外排序的k路平衡归并中使用，它是一个完全二叉树，其非叶节点为比较中的败者。根节点为最后一次比较的败者。最终胜利者则被直接输出（或到输出缓冲区）。

败者树的引入是因为：k路平衡归并中，若不使用败者树，则对每次对k路需要比较k-1次得到最值，对于总共n个记录的每一趟归并共需要(n-1)*(k-1)次比较。若有m个归并初始段，归并趟数为logk(m) ,总共比较次数logk(m)*(n-1)*(k-1)。引入败者树（由k个元素构造成败者树）则每次不需要k-1次比较，只需要log2（k）次即可。