0
$\begingroup$

I am confused why Binomial heaps do not utilize marking.

Concerning Fibonacci heap children:

Each tree in a Fibonacci heap is allowed to lose at most two children before      
that tree needs to be "reprocessed" at a later step. The marking step in the  
Fibonacci heap allows the data structure to count how many children have 
been lost so far. An unmarked node has lost no children, and a marked node 
has lost one child. Once a marked node loses another child, it has lost two 
children and thus needs to be moved back to the root list for reprocessing.  

How do Binomial heaps not need marking? It seems like in Fibonacci, this is in place so that when a marked node loses another child, it knows to move it back to the root and reprocess. I do not understand how Binomial heaps can possibly handle this without marking.

$\endgroup$

1 Answer 1

1
$\begingroup$

In binomial heaps the structure of the trees in the heap is very strict, they all have a number of elements that is a power of two. When a node is removed it is the root of a tree, and all the children (which are again roots trees with a power of two elements) are merged with the other original trees.

There are no nodes that have an "imperfect" number of children, and there is no marking needed to indicate that.

$\endgroup$
2
  • $\begingroup$ can you clarify what you mean with "imperfect" number of children? Thank you $\endgroup$
    – Carlo
    Mar 31, 2016 at 0:11
  • $\begingroup$ Look at the pictures of binomial heaps on wikipedia. They do not loose children, unlike Fibo heaps. But in Fibo heaps you do not want to loose too much children because of efficiency, hence the marking. $\endgroup$ Mar 31, 2016 at 1:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.