Cascade heap: towards time-optimal extractions (Q5919538)

The paper describes a priority queue data structure that supports insertion in constant time and where the \(k\)th delete-minimun operation takes time \(O(\log^* n+\log k)\) where \(\log^*\) denotes the iterated logarithm. This constitutes an improvement over the state of the art when the number of insertions is much smaller than the number of delete-minimum operations. Unfortunately, the result is somewhat difficult to read. The employed data structure is an elegant recursive construction based on heaps -- it can contain heaps of heaps, heaps of heaps of heaps, etc. The basic data structure allows for amortized complexity bounds. This result is then de-amortized. A small problem is that no example of the recursive heap is given, which somewhat limits the accessibility of the result. The authors note that the data structure looks practical but that initial implementation attempts did not yield performance competitive with previous data structures.