L27 Slides

We finished our discussion of reductions, and I introduced a data structure that allows you to perform dictionary queries on keys. When the universe is limited to some range of keys $[1,\ldots,N]$, this data structure, the van Emde Boas queue, allows all operations to proceed in $\log\log N$ time, which is an improvement over standard balanced binary trees, hash tables, and bit-vectors. The interesting aspect is that this queue employs the idea of divide-and-conquer to a data structure.