The previous TimeoutFactory priority queue is not gernalized as its coupled to the TimeoutImpl details. There is a org.jboss.util.Heap which could be used instead.

Here is one acm article that claims an integer priority queue with O(log log n) delete operations:

http://portal.acm.org/citation.cfm?id=780566

We consider Fibonacci heap style integer priority queues supporting insert and decrease key operations in constant time. We present a deterministic linear space solution that with n integer keys support delete in O(log log n) time. If the integers are in the range [0,N), we can also support delete in O(log log N) time.Even for the special case of monotone priority queues, where the minimum has to be non-decreasing, the best previous bounds on delete were O((log n)1/(3-?)) and O((log N)1/(4-?)). These previous bounds used both randomization and amortization. Our new bounds a deterministic, worst-case, with no restriction to monotonicity, and exponentially faster.As a classical application, for a directed graph with n nodes and m edges with non-negative integer weights, we get single source shortest paths in O(m+n log log n) time, or O(m+n log log C) if C is the maximal edge weight. The later solves an open problem of Ahuja, Mehlhorn, Orlin, and Tarjan from 1990.

I can't tell from the link if this is an arbitrary delete or just the deleteMin. Given the time bound its probably just the deleteMin, not deletion of an arbitary element.