Fibonacci Heap 是否可以有多个具有相同等级（或值，或键）的节点？

Question

我一个人在研究斐波那契堆，遇到一道题

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

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)

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

Answer 1

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

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

斐波那契堆就是这些树的集合。如果不止一个根有最小键，那么任何这样的根都可以是最小节点。

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

Can Fibonacci Heap have more than one nodes with equal rank(or value, or key)?