Data-structural bootstrapping examples?

Question

I recently read Okasaki and Brodal's paper "Optimal Purely Functional Priority Queues," which describes a fast priority queue based on data-structural bootstrapping, in which a simple and inefficient data structure is used to construct a robust and efficient structure. This seems like a really beautiful theoretical idea, but so far the only example I know of is the one from this paper.

Does anyone have any other examples of data-structural bootstrapping that would be a good starting point for further reading on the subject?

Answer 1

Chris Okasaki's thesis has a whole chapter on data-structural bootstrapping, including some other examples and references to papers with even more.