The van Emde Boas tree is a recursive data structure that can provide the implementation of an integer priority queue. Taking advantage of integers, it can provide all operations in O(lg lg u) time.

Please see the Wiki for discussion of implementation.

Keith Schwartz has a nice implementation in his Archive of Interesting Code.

Good news (30/7/2014): after coming back to play with the code after a year's hiatus, due to an improvement in compilers, my C++ knowledge, or both, everything now works as originally designed and is quite fast! (Faster even than Keith's!)

Here are the benchmark results in nanoseconds per find operation: Finding t from 8 up to 2097152 elements at: Wed Jul 30 17:04:21 2014 size bsrch set hash van Emde Boas tree 8 7 6 12 2 16 9 9 14 2 32 18 26 13 2 64 37 36 18 4 128 56 43 22 6 256 57 48 20 7 512 58 54 20 12 1024 69 60 20 12 2048 71 70 20 14 4096 75 85 23 15 8192 84 109 27 19 16384 92 147 29 25 32768 101 230 32 21 65536 110 235 24 26 131072 149 263 18 21 262144 146 230 23 21 524288 173 236 36 22 1048576 221 229 35 21 2097152 382 243 31 22 (bsrch = boost::flat_set, set = std::set, hash = std::unordered_set.)