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?”

  • $\begingroup$ I assume you're looking for something even simpler than hollow heaps and quake heaps? $\endgroup$
    – jbapple
    May 8, 2021 at 20:16
  • $\begingroup$ @jbapple If possible, yes. Those structures are indeed simpler than a Fibonacci heap, but still involve a number of sub steps that are tough to justify without knowledge of the bigger picture (give trees ranks, combine trees of different ranks until there’s at most one tree of each rank, move nodes during a decrease-key, performing a fixup if some constraint is violated, etc.) $\endgroup$ May 9, 2021 at 15:21
  • $\begingroup$ Quake heaps seem pretty nice and simple to implement. And analysis is also quite clean. Timothy Chan's paper is only 3.5 to 4 pages. Randomization can be subtle and hard to understand in terms of analysis even if the implementation is simple. $\endgroup$ May 10, 2021 at 3:28
  • $\begingroup$ @ChandraChekuri Oh, definitely. They’re a very nice structure. I’ve found that in many cases randomized data structures shift the complexity from the implementation into the analysis, which is why I was curious about whether there’s a “dead simple” randomized priority queue that has the needed time bounds. If so, its analysis might be tricky, but it would be interesting to explore. $\endgroup$ May 10, 2021 at 3:36


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy