Treap Split and Merge

Problem

values is sorted ascending and priorities define a treap (a max-heap on priorities, so the highest priority becomes the root). Build the treap recursively, split it into values < key and values >= key with the standard recursive treap split, then merge the two parts back with the recursive treap merge. Return [left_preorder, right_preorder, merged_preorder].

Hint

Split cuts below a node when its value is smaller than the key and above it otherwise; merge undoes the cut.

Test cases

case 1

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

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

case 2

in: [[10,20,30],[1,3,2],20]

expected: [[10],[20,30],[20,10,30]]

case 3

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

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

case 4

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

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

Starter codePython

def treap_split_merge(values, priorities, key):
    # Your code here
    pass

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