As we know treap is the combination of Tree and Heap. It is a tree like structure that has a
rigid order when traversed.
We can find the lowest value or the lower value than
K near a given position.
Treap
Tree Structure
- As heap it contains the smallest item near the root.
- As tree, when traversed in-order, it gives the items in sequential order we inserted them.
That means that we can insert an item at certain position.
Benefits
We can find the lowest value or the lower value than `K` **near** a given position.
Drawbacks
Treap is not a balanced tree. So the cost of lookup is not always logN.
Treap on top of a Segment Tree
Segment tree structure
- It has all the values in the leaves.
- All internal nodes that are not leaves contains the minimum value in the subtree.
Benefits
The query is logN.
Drawbacks
My implementation is fixed size.
My treap
The full implementation is
here in this project.
You are welcome to try this for example in this problem,
