AlgorithmsThread 9: Treaps!

Welcome back to another episode of Algorithms Thread. Today we learn about Treaps, one way of coding them, and some very powerful things they can do.


After you watch this, check out the high-quality Codeforces Gym set that I made which you can use to practice your Treap skills as a challenge to make sure you really learned this topic:

Github with Treap code: https://github.com/SecondThread/Algor...

Timestamps:
0:00 Good Morning

0:20 Prereqs and Gym Set
2:11 Treap uses
4:55 Binary Search Tree Constraints
8:08 Forcing Log Height
10:00 Making Priorities
12:00 Treap Splitting
16:05 Merging
20:30 Implementation Details
31:24 Doing Arbitrary Queries
33:57 Runtime Analysis
35:03 MIRRORING (and going outside)
38:50 Implementing reflection
39:55 Finding parents
42:55 Gotchas