A treap is a height balanced binary tree. It is used to store a sequence in a tree, which allows for various applications like searching. A Cartesian tree, in case of a sorted sequence, would be basically a linked list, making tree virtually useless. Treap is used to solve such cases by using random priority for each node.
Thus treap is a balanced binary tree with heap properties.
Read this article to understand Treap in depth
Have a doubt or thought? Join the discussion now
This is a companion discussion topic for the original entry at http://iq.opengenus.org/treap-randomized-cartesian-tree/