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