One question and one suggestion.
The question: Why would I use a Treap and what benefits (and costs) would result as compared to using a normal hash for that (those) same applications?
The Suggestion: If you get around to modifying the interface to take a single custom comparator rather than the two as now (which I think makes a lot of sense), then you might also consider making the standard alpha comparator (cmp) a settable option in place of the default numeric comparator. That is to say, have a new()/tie() time option that can be set to indicate that the caller wants an alpha-sort order used rather than a numeric and then use cmp rather than <=> internally to the module rather than requiring the user to supply a comparator function that does this.
The main reason is that callbacks can be expensive. The best demonstration of this is the GRT. Even though performing a numeric sort using a GRT requires stringifying the numeric (part of the) values to be sorted, into numerically orderable strings (ie. fixed width with leading zeros), this pre-sort overhead is more than compensated for by performance gained by avoiding the need to callback into user code for the comparisons during the sort. I think that the overhead of an if or trinary conditional in the module code to determine which operator to use when inserting and/or balancing (is that the right term with a Treap?) would be easily offset by the benefit of not invoking a callback for the common cases of a 'trivial comparator', ie. numeric or alpha.
As an aside. I've long wished that perl had a numeric sort option built in (would one extra built-in called sortn be any great burden?), so that many cases where sorting numerically currently requires the overhead of a trivial callback or user block, or resorting to the GRT (or tyes recently posted variation on the theme) would become unnecessary.
Examine what is said, not who speaks."Efficiency is intelligent laziness." -David Dunham
"When I'm working on a problem, I never think about beauty. I think only how to solve the problem. But when I have finished, if the solution is not beautiful, I know it is wrong." -Richard Buckminster Fuller
If I understand your problem, I can solve it! Of course, the same can be said for you.