Surprising and basic data structures
I would not know what you learned or did not learn, What is surprising depends a lot on who is to be surprised. So your question is pretty much undefined.

All I can do for you (but I am no expert) is to mention one technique that impressed me when I first saw it, the skip lists of William Pugh. And more generally the use of randomness and  probabilistic techniques, actually not just in algorithmics but also in "proving" or in quickly identifying things that can then be formally proved (at high computational cost) to have this or that property.