suvro_coder's blog

Need help in implementing treaps using arrays!
By suvro_coder, history, 6 years ago, In English

Can anyone provide me some source to learn treaps which is implemented using arrays. I got some source to understand it from this quora thread https://threads-iiith.quora.com/Treaps-One-Tree-to-Rule-em-all-Part-1 but I'm not getting the code. Some array solution like that of segment trees would have been helpful. Thank you.

  • Vote: I like it
  • +14
  • Vote: I do not like it

Comments Comments (1)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can't implement treaps implicitly in an array unlike segment trees since treaps are not complete binary trees. You could use array indexing instead of using pointers (i.e. arena allocation), but that would be more complicated. The best way is to use pointers and new to allocate a new node. Check out the CP Algorithms article on treap.

→ Reply