Leftist Heap Merge Swap Count

Problem

Build leftist heaps by inserting a_values and b_values one at a time with merge, then merge the two heaps together. In each recursive merge the smaller root is kept, its right child becomes the merge of its old right child with the other heap, and the node swaps its two children whenever the left null-path length is smaller than the right one. Return the total number of child swaps performed.

Hint

Each merge unwinds along the right spine; a swap restores the leftist property before returning.

Test cases

case 1

in: [[3,1],[2]]

expected: 1

case 2

in: [[5],[4,6]]

expected: 1

case 3

in: [[],[1,2]]

expected: 1

case 4

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

expected: 2

Starter codePython

def leftist_merge_swaps(a_values, b_values):
    # Your code here
    pass

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