van Emde Boas Trees

The van Emde Boas tree or van Emde Boas priority queue is a data structure supporting membership test, insertion, predecessor and successor search, minimum and maximum determination and deletion in O(log log U) time, where U = 0,...,2^n-1 is the overall range to be considered.

The presented formalization follows Chapter 20 of the popular Introduction to Algorithms (3rd ed.) by Cormen, Leiserson, Rivest and Stein (CLRS), extending the list of formally verified CLRS algorithms. Our current formalization is based on the first author's bachelor's thesis.

First, we prove correct a functional implementation, w.r.t. an abstract data type for sets. Apart from functional correctness, we show a resource bound, and runtime bounds w.r.t. manually defined timing functions for the operations.

Next, we refine the operations to Imperative HOL with time, and show correctness and complexity. This yields a practically more efficient implementation, and eliminates the manually defined timing functions from the trusted base of the proof.