Treap (Cartesian tree)
Summary
Treap, also known as Cartesian tree, is a data structure combining a BST by X and a heap by Y. The article explains definitions, advantages, core operations (insert, search, erase, build, union, intersect), and the essential Split and Merge algorithms with implementation details and notes on implicit treaps and subtree sizes.