A standard implementation of Fibonacci heaps requires four pointers per node (pa

Question

A standard implementation of Fibonacci heaps requires four pointers per node (parent, child, and right and left siblings).

*** Please write any code required in C
a) Show how you would implement Fibonacci heaps using only three pointers per node.


b) Assume that the insert(F, x) operation on Fibonacci heaps is defined as follows:
degree(x)=0;
parent(x)=Null;
child(x)=Null;
left(x)=x;
right(x)=x;
add x to the root list;
if(min(F)==Null OR key(x)size(F)=size(F)+1;
Describe the same operation for the 3-pointer implementation scheme.


c) Illustrate how the two implementation schemes work by applying
insert (F, 6) when F is the following Fibonacci heap:
7->{24, 17, 23}|24->{26, 46}|17->{30}|26->{35} <+>
18->{21, 39}|21->{52}} <+> 38->{41}
where <+> separate different trees, arrows point to children,
and vertical bars continue the description of a tree at lower levels.
Review the implementation of Fibonacci heaps presented in Week 6.
A standard implementation of Fibonacci heaps requires four pointers per node (parent, child, and right and left siblings).

*** Please write any code required in C
a) Show how you would implement Fibonacci heaps using only three pointers per node.


b) Assume that the insert(F, x) operation on Fibonacci heaps is defined as follows:
degree(x)=0;
parent(x)=Null;
child(x)=Null;
left(x)=x;
right(x)=x;
add x to the root list;
if(min(F)==Null OR key(x)size(F)=size(F)+1;
Describe the same operation for the 3-pointer implementation scheme.


c) Illustrate how the two implementation schemes work by applying
insert (F, 6) when F is the following Fibonacci heap:
7->{24, 17, 23}|24->{26, 46}|17->{30}|26->{35} <+>
18->{21, 39}|21->{52}} <+> 38->{41}
where <+> separate different trees, arrows point to children,
and vertical bars continue the description of a tree at lower levels.
Review the implementation of Fibonacci heaps presented in Week 6.

Explanation / Answer

void Fibonancci_heaps(int *p1, int p2*, int *p3) { *p1=1; *p2=1; for(int i=0; i

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.