How to show Fibonacci heap with n nodes can have h

Question

I want to show that a Fibonacci heap with n nodes could have height n.

I tried this with examples but I don't know how to show this in general.

Answer 1

(I assume you mean height n - 1: height n is impossible since with n nodes the maximum height is a linked list of height n - 1)

Getting to height one is easy: add in three nodes, then do a dequeue-min. This removes one node and combines the other two nodes, which have height 0, into this structure of height 1:

A
|
B

If you repeat this process again and ensure one of the new nodes has the lowest priority, you get two of these trees, which are then merged together like this:

A
|\
B C
  |
  D

Now, do a delete operation on B. This leaves A with order 1 and a mark:

A*
|
C
|
D

Repeat this process again (insert three nodes, all of which have infinite negative priority, and call dequeue-min) to get this:

E
|\
F A*
  |
  C
  |
  D

Delete F to get

E*
|
A*
|
C
|
D

If you repeatedly execute this process of adding three nodes, deleting one, then deleting the singleton child of the single remaining tree, you can make the Fibonacci heap a single tree of height n - 1 for any n you'd like.

Hope this helps!