首页 > 试题广场 >

(2-3-4堆)对于2-3-4树,树中每个内部节点(而不是根

[问答题]
(2-3-4堆)对于2-3-4树,树中每个内部节点(而不是根)有2个,3个或4个孩子,且所有的叶节点有相同的深度。在本问题中,实现支持可合并堆操作的2-3-4堆。
        2-3-4堆一下几点与2-3-4树不同。在2-3-4堆中,仅仅叶节点存储关键字,并且每个叶节点x仅仅在属性x.key中存储一个关键字。叶节点中的关键字可能以任意顺序产生,每个内部节点x包含一个值x.small,它等于以x为根的子树中叶节点存储的最小的关键字。根r包含一个属性r.height,存储树的高度。最后,2-3-4堆设计为存放在主存中,这样存盘的读写是不需要的。
       实现下面的2-3-4堆操作,在一个具有n个堆上的2-3-4树上,(a)~(e)每一个操作应在O(lgn)时间内完成。(f)中的UNION操作应在O(lgn)时间内完成,其中n为输入的两个堆的元素个数之和。
a.MINIMUM,该操作返回一个指向具有最小关键字的叶节点的指针。
b.DECREASE-KEY,该操作将一个给定的节点x的关键字减小为给定的值
c.INSERT,该操作插入一个关键字为k的叶节点x.
d.DELETE,该操作删除一个给定的叶节点x.
e.EXTRACT-MIN,该操作抽取具有最小关键字的叶节点。
f.UNION,该操作合并两个2-3-4堆,并返回一个单独的2-3-4堆,销毁掉输入的堆。

这道题你会答吗?花几分钟告诉大家答案吧!