Leftist Heap Merge Rank

Problem

Merge two leftist heaps built from insertion lists and report values with their ranks.

A leftist node is [value, left, right, rank] where rank is the null-path length. Merge keeps the smaller root, merges its right child, then ensures the left child has the larger rank. Values are inserted one at a time by merging singleton nodes.

Return the preorder traversal as [value, rank] pairs.

Hint

The rank is one plus the rank of the right child, after swapping to keep it smaller.

Test cases

case 1

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

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

case 2

in: [[10,20],[15,30,5]]

expected: [[5,2],[15,1],[30,1],[10,1],[20,1]]

case 3

in: [[],[]]

expected: []

case 4

in: [[7],[]]

expected: [[7,1]]

Starter codePython

def leftist_heap_merge(values_a, values_b):
    # Your code here
    pass

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