首页 > 试题广场 >

“败者树”中的“败者”指的是什么？若利用败者树求k个数中的最

[问答题]
“败者树”中的“败者”指的是什么？若利用败者树求k个数中的最大值，在某次比较中得到a>b，那么谁是败者？“败者树”与“堆”有何区别？
添加回答
推荐
赞花婆头像 赞花婆
b是败者。败者树与堆的最大差别在于：败者树是由参加比较的n个元素作为叶子结点而得到的完全二叉树，而“堆”则是n个元素Ri(i=1,2,…，n)的序列，它满足系列性质Ri≤R2i且Ri≤R2i+1（1≤i≤[n/2]）。由于这个性质中下标i和2i，2i+1的关系恰好是和完全二叉树中第i个结点和它的孩子结点的序号之间的关系一致，则堆可看成是含n个结点的完全二叉树。
发表于 2018-03-25 09:31:17 回复(0)
木板与钉子头像 木板与钉子
在找最小值时，败者指的是一次pk中较大的叶子节点。
b是败者
败者树是非叶子节点存储的是败者，而堆的父节点的值要么大于等于其左右子节点的值，或者是小于等于其左右子节点的值。也就是堆的所有节点存储的是有效数据，而败者树非叶子节点存储的是有效数据（叶子节点）pk中产生的败者。
发表于 2018-08-09 21:02:58 回复(0)
提交观点

问题信息

树 堆
上传者：赞花婆
难度：
2条回答 2891浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号