Treaps visualizer

The Partridge Family were neither partridges nor a family. Discuss.
Post Reply
User avatar
MyK_00L
Posts: 19
Joined: June 21st, 2016, 10:44 am

Treaps visualizer

Post by MyK_00L » July 27th, 2018, 12:17 pm

It has been quite a while since I last used the chili framework.
It has been too much time.
Also I just learned treaps, so I guessed I might as well make this thing. :D
It's not meant to help someone learn treaps: I simply put random operations each frame depending on what key you are pressing (It's quite trippy), but if you want to get user input decently so that you can actually see what the ds(data structure) is doing it shouldn't be too hard.
The code in Treap.h is not organized too well, but it should be understandable.
Also I just discovered that if you want to make a template class you have to put both declarations and implementation in the same file? wtf :?:
If you want me to add some features or something just ask here.
If you download this you should probabilly be entratainded for about 1 to 12 seconds.
inputs are:
  • I for insert
  • E for erase
  • R for rotate
The only thing this could actually be useful for is convincing someone that the height of a treap IS going to be logarithmic.
Also feel free to ask anything about how treaps work.
And if you notice a mistake of mine please tell me so that I won't do it again.

have fun?

P.S.
I also wanted to post this in the forum so that people reading this might get into the world of algorithms and competitive programming, which is super fun and cool. :D
Attachments
TreapVisualizer.zip
here's the code
(107.09 KiB) Downloaded 239 times

User avatar
chili
Site Admin
Posts: 3948
Joined: December 31st, 2011, 4:53 pm
Location: Japan
Contact:

Re: Treaps visualizer

Post by chili » July 27th, 2018, 2:42 pm

Interesting, never really knew about 'treaps' had to google it. Seems interesting, like an alternative to balanced trees maybe.
Chili

User avatar
MyK_00L
Posts: 19
Joined: June 21st, 2016, 10:44 am

Re: Treaps visualizer

Post by MyK_00L » July 27th, 2018, 2:50 pm

chili wrote:Interesting, never really knew about 'treaps' had to google it. Seems interesting, like an alternative to balanced trees maybe.
Treaps are balanced trees :)
The difference from other balanced trees are:
  • treaps are randomized
  • treaps can do alot of things: insert, erase, rotate a subsequence, split it in two, merge it back together, and it can also do everything a range tree can do. All of this in log(n) time
also treaps are fairly easy to implement.

Post Reply