Difference between Binomial and Fibonacci heap (marking)

I am confused why Binomial heaps do not utilize marking.

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.

1 Answer

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.

• can you clarify what you mean with "imperfect" number of children? Thank you – Carlo Mar 31 '16 at 0:11
• 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. – Hendrik Jan Mar 31 '16 at 1:21