Treap Insert by Priority Seeded

Problem

Insert values into a treap and return the preorder traversal.

values and priorities are parallel lists; each value is inserted as in a BST with the given priority, then rotated up while its priority exceeds its parent's (a max-heap on priorities). Duplicate values are ignored.

Return the preorder list of values (node, then left, then right).

Hint

After inserting into a subtree, rotate if the child's priority is now higher than the node's.

Test cases

case 1

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

expected: [8,3,5]

case 2

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

expected: [3,2,1]

case 3

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

expected: [1,2,3]

case 4

in: [[10],[5]]

expected: [10]

case 5

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

expected: [2,1,3]

Starter codePython

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

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