Binomial Heap Union Step

Problem

Perform the linking phase of a binomial heap union.

Each heap is a list of [degree, root_value] trees sorted by degree. Combine the two lists, then repeatedly link two trees of equal degree: the smaller root becomes the parent and the new degree increases by one. Continue until every degree appears at most once.

Return the resulting list of [degree, root_value] sorted by degree.

Hint

Linking two degree-d trees always produces one degree-(d+1) tree.

Test cases

case 1

in: [[[0,5]],[[0,3]]]

expected: [[1,3]]

case 2

in: [[[0,1],[1,4]],[[0,2]]]

expected: [[2,1]]

case 3

in: [[[1,5]],[]]

expected: [[1,5]]

case 4

in: [[[0,9],[2,4]],[[0,3],[2,7]]]

expected: [[1,3],[3,4]]

Starter codePython

def binomial_union_step(heap_a, heap_b):
    # Your code here
    pass

4 test cases · run your code against them in the editor