Optimal Worst-Case Operations for Implicit Cache-Oblivious Search Trees

We close an open issue on dictionaries dating back to the sixthies. An array of n keys can be sorted so that searching takes O(log n) time. Alternatively, it can be organized as a heap so that inserting and deleting keys take O(log n) time. We show that these bounds can be simultaneously achieved in the worst case for searching and updating by suitably maintaining a permutation of the n keys in the array. The resulting data structure is called implicit as it uses just O(1) extra memory cells beside the n cells for the array. The data structure is also cache-oblivious, attaining O(log_Bn) block transfers in the worst case for any (unknown) value of the block size B, without wasting any single cell of memory at any level of the memory hierarchy.