If we insert a set of n items into a binary search tree the resulting tree may be unbalanced.

In this question, you will investigate an alternative approach using a treap. A treap is a binary search tree with a modified way of ordering the nodes with respect to the key values ki and a min-heap with respect to the priority pi .

Consider a set of records R = {r1, r2, . . . rn}. Each record ri has a key ki and independently of ki a priority pi . We will write a record as (ki , pi). The records are inserted into the treap such that the binary-search-tree property based on the records key value is maintained and the priorities obey the min-heap order property.

You may assume that all key values and priorities are positive integers, and all priorities are distinct as well.

Write an algorithm BuildTreap(R) in pseudocode to construct a treap from the set of records R passed as an argument to your function. (Hint: use recursion) You must include appropriate comments in your pseudocode. Your pseudocode should make reasonable assumptions about how trees are represented.

In addition, you may like to use:

T ? new T ree to create a new tree;

T.key ? k and T.priority ? p can be used to set the record attribute (field) integer values;

null can be used to represent an empty tree

Very Important, MUST BE IN PSEUDO-CODE