Since the Fibonacci heap was developed, many other priority queues have been invented with equivalent time bounds and a simpler design (e.g. hollow heaps, quake heaps, etc.).
Many classical worst-case efficient data structures have related randomized data structures that meet the same time bounds on expectation (e.g treaps and zip trees for sorted dictionaries, randomized incremental trapezoids for point location, cutset structures for dynamic connectivity, etc.). However, the only randomized priority queue I’ve encountered is the randomized meldable heap, which doesn’t meet the same time bounds as the Fibonacci heap (particularly for decrease-key).
Are there any known randomized data structures that meet the Fibonacci heap time bounds with a “simpler” implementation, for some subjective definition of “simpler?”