Synergistic Sorting, MultiSelection and Deferred Data Structures on MultiSets

Jérémy Barbay, Carlos Ochoa, Srinivasa Rao Satti

Karp et al. (1988) described Deferred Data Structures for Multisets as "lazy" data structures which partially sort data to support online rank and select queries, with the minimum…