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.
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
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
add node x to the beginning of H's list of roots
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).