0

我正在单独研究斐波那契堆，我遇到了一个问题。

我知道任何节点都可以插入斐波那契堆，但是如果该新节点的等级（或值或键）等于兄弟节点怎么办？

1）例如，

   (1) <-minimum root
  /   \
(3)   (5)

如果插入（1）的节点会发生什么？

(1) --- (1)
       /   \
     (3)   (5)

2）或者在这种情况下会发生什么？

前：

 (2)-----(4)-----(5)
  |      / \     / \
 (1)   (6) (7) (8) (9)

后：

 (2)-----(4)-----(5)    +     (5)
  |              / \          / \
 (1)           (8) (9)      (1) (2)

新的节点树属于哪里？

3）你将如何整合（或排序）这种树 - 在根部有一对相等的节点？

 (10) ---- (10) ----- (1) ----- (3) ----- (4)

如果有人能帮我解决斐波那契堆上的这个小困惑，我将不胜感激。谢谢你。

4

1 回答 1

0

具有相同键的节点是可以的。

回想一下堆属性：对于min-heap，每个节点的键都大于 或等于其父节点的键。（可以类似地定义最大堆属性。）

斐波那契堆只是这些树的集合。如果多个根具有最小键，则任何这样的根都可以是最小节点。

在你的例子中，（1）和（3）没有错。但是在 (2) 中，您的树违反了最小堆属性。

于 2015-05-26T13:21:33.293 回答