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.