<p>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.).</p>
<p>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).</p>
<p>Are there any known randomized data structures that meet the Fibonacci heap time bounds with a “simpler” implementation, for some subjective definition of “simpler?”</p>

CC BY-SA 4.0
2021-05-08T20:16:09.420Z
I assume you're looking for something even simpler than hollow heaps and quake heaps?
jbapple
CC BY-SA 4.0
2021-05-09T15:21:02.947Z
@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.)
templatetypedef
CC BY-SA 4.0
2021-05-10T03:28:06.467Z
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.
Chandra Chekuri
CC BY-SA 4.0
2021-05-10T03:36:34.197Z
@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.
templatetypedef
<soft-question><ds.data-structures><randomized-algorithms>
Simple randomized priority queue matching the Fibonacci heap time bounds?
templatetypedef
# Simple randomized priority queue matching the Fibonacci heap time bounds?

(Asked by: username_0 on 2021-05-08)

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

**Tags:** soft-question, ds.data-structures, randomized-algorithms
> **Comments:**
> **username_1**: I assume you're looking for something even simpler than hollow heaps and quake heaps?  
> **username_0**: @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.)  
> **username_2**: 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.  
> **username_0**: @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.  

---

## 0 answers

