Problem Detail: 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.
Asked By : Carlo
Answered By : Hendrik Jan
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/55206
