Fibonacci heap: Difference between revisions

Content added Content deleted
Line 86: Line 86:
return _find(heap,value);
return _find(heap,value);
}
}

void display() const { // function code adapted from GO code just below C++
node<V>* p = heap;
if (p == NULL) {
cout << "The Heap is Empty" << endl;
return;
}
cout << "The root nodes of Heap are: " << endl;
_display_tree(heap, "");
cout << endl;
}

private:
private:
node<V>* _empty() {
node<V>* _empty() {
Line 165: Line 177:
if(t==n)break;
if(t==n)break;
trees[n->degree]=NULL;
trees[n->degree]=NULL;
t->prev->next=t->next;
t->next->prev=t->prev;
if(n->value<t->value) {
if(n->value<t->value) {
t->prev->next=t->next;
t->next->prev=t->prev;
_addChild(n,t);
_addChild(n,t);
} else {
} else {
t->prev->next=t->next;
t->next->prev=t->prev;
if(n->next==n) {
if(n->next==n) {
t->next=t->prev=t;
t->next=t->prev=t;
_addChild(t,n);
n=t;
} else {
} else {
n->prev->next=t;
n->prev->next=t;
Line 181: Line 189:
t->next=n->next;
t->next=n->next;
t->prev=n->prev;
t->prev=n->prev;
_addChild(t,n);
n=t;
}
}
_addChild(t,n);
n=t;
}
}
continue;
continue;
Line 209: Line 217:
n->next=n->prev=n;
n->next=n->prev=n;
n->marked=false;
n->marked=false;
n->parent->degree--;
return _merge(heap,n);
return _merge(heap,n);
}
}
Line 215: Line 224:
if(n->value<value)return heap;
if(n->value<value)return heap;
n->value=value;
n->value=value;
if(n->value<n->parent->value) {
node<V>* parent = n->parent;
if(parent != nullptr && n->value < parent->value) {
heap=_cut(heap,n);
heap=_cut(heap,n);
node<V>* parent=n->parent;
n->parent=NULL;
n->parent=NULL;
while(parent!=NULL && parent->marked) {
while(parent!=NULL && parent->marked) {
Line 226: Line 235:
}
}
if(parent!=NULL && parent->parent!=NULL)parent->marked=true;
if(parent!=NULL && parent->parent!=NULL)parent->marked=true;
if (n->value < heap->value)heap = n;
}
}
return heap;
return heap;
Line 241: Line 251:
return NULL;
return NULL;
}
}

};</lang>
void _display_tree(node<V>* n, string pre) const {
string pc = "│ ";
node<V>* x = n;
do {
if (x->next != n) {
cout << pre << "├─";
} else {
cout << pre << "└─";
pc = " ";
}
if (x->child == nullptr) {
cout << "─" << x->value << endl;
} else {
cout << "┐" << x->value << endl;
_display_tree(x->child, pre + pc);
}
// cout << endl;
x = x->next;
} while (x != n);
}

};

/*
* main() for testing constructor, getMinimum(), display(), removeMinimum(), decreaseKey(), isEmpty()
*/
int main(int argc, char** argv) {

FibonacciHeap<int> fh;

fh.insert(23);
fh.insert(7);
fh.insert(21);
fh.insert(3);
fh.insert(17);
fh.insert(24);
fh.insert(18);
fh.insert(52);
fh.insert(38);
fh.insert(30);
fh.insert(26);
fh.insert(46);
node<int>* n = fh.insert(39);
node<int>* m = fh.insert(41);
fh.insert(35);

cout << "Heap Minimum: " << fh.getMinimum() << endl;
cout << "The Heap is: " << endl;

fh.display();
cout << "Heap Minimum Extracted: " << fh.removeMinimum() << endl;
fh.display();

cout << "de: " << n->getValue() << " para: 5" << endl;
fh.decreaseKey(n, 5);

cout << "Heap Minimum: " << fh.getMinimum() << endl;
fh.display();

cout << "de: " << m->getValue() << " para: 2" << endl;
fh.decreaseKey(m, 2);

while (!fh.isEmpty()) {
cout << "Heap Minimum Extracted: " << fh.removeMinimum() << endl;
fh.display();
}

return 0;
}

</lang>


=={{header|Go}}==
=={{header|Go}}==
Retrieved from "https://rosettacode.org/wiki/Fibonacci_heap"