Why search the heap first?  I'd have thought we'd search:

 * The 10ms bucket that should contain it (O(1))
 * The 1s bucket that should contain it (O(1))
 * The heap (O(N))
 * Optionally (panic stations!):
     * All the 10ms buckets (O(100))
     * All the 1s buckets (O(3600))