Question: instead of using union to perform an insert into a...

Instead of using Union to perform an Insert into a binomial heap H, we can write code that directly does the insert. Note that we keep the list of roots of H sorted by degree.

Insert(H, item)

let x be a pointer to a new node x with Nil in its parent, child and sibling pointers

x.key = item

x.degree = 0

loop

let y be a pointer to the rst root in H's list of roots

exit when y = Nil or x.degree 6 =/ y.degree

remove the node that y points to from H's list of roots

if x.key > y.key then swap the pointers x and y

make node y the first child of node x  

end loop

add node x to the beginning of H's list of roots

end Insert

Use the potential method to show that the total time required to do a sequence of m Inserts on an initially empty binomial heap is O(m).