Van Emde Boas priority queue

In computer science , the Van Emde Boas priority queue , which is named after its inventor Peter van Emde Boas , is an efficient implementation of a priority queue in which the actions insert, delete, GetMinimum etc. have a running time of O (log log N) where N is the number of possible keys.

construction

A Van Emde Boas priority queue consists of a k-structure T, where k indicates the maximum number of bits that each element may need for representation, with the following properties:

• T.size: Number of all elements that are currently stored in the priority queue
• T.list: Doubly linked list that contains the stored keys in ascending order
• Tb: a bit vector with Tb [i] = ${\displaystyle {\begin{cases}1&i\in T.list\\0&sonst\\\end{cases}}}$
• Tp: A vector of pointers to the elements of T.list. If Tb [i] = 1, then Tp [i] points to i in T.list.
• T.top: The same k / 2 structure described here, which contains the first half of the bits of all keys contained in T.list
• T.bottom: A field with k / 2 structures, each of which contains an entry for the elements of T.top, with the content of the last half of the bits belonging to the front half.

example

Be the key set . ${\displaystyle k=4}$ ${\displaystyle S=\{2,3,7,10,13\}}$

• Then T.size ${\displaystyle =5}$
• T.list contains the keys from S doubly concatenated in ascending order.
• Tb [2] Tb [3] Tb [7] Tb [10] Tb [13] . ${\displaystyle =}$ ${\displaystyle =}$ ${\displaystyle =}$ ${\displaystyle =}$ ${\displaystyle =1}$
• Tp [2] points to in T.list, Tp [3] to etc. ${\displaystyle 2}$ ${\displaystyle 3}$

For T.top and T.bottom, the binary values ​​of the stored numbers must be considered. , , , , . ${\displaystyle 2_{10}=0010_{2}}$ ${\displaystyle 3_{10}=0011_{2}}$ ${\displaystyle 7_{10}=0111_{2}}$ ${\displaystyle 10_{10}=1010_{2}}$ ${\displaystyle 13_{10}=1101_{2}}$

• T.top is 2-structure for the values . ${\displaystyle \{00_{2},01_{2},10_{2},11_{2}\}=\{0,1,2,3\}}$
• T.bottom has 4 entries (one for each element from T.top) with
  • T.bottom [0] , ${\displaystyle =\{10_{2},11_{2}\}=\{2,3\}}$
  • T.bottom [1] , ${\displaystyle =\{11_{2}\}=\{3\}}$
  • T.bottom [2] , ${\displaystyle =\{10_{2}\}=\{2\}}$
  • T.bottom [3] . ${\displaystyle =\{01_{2}\}=\{1\}}$

A key with cannot be saved in this 4-structure, since more than 4 bits would be required for storage. ${\displaystyle x}$ ${\displaystyle x>=16}$ ${\displaystyle 2^{4}=16}$

literature

• P. van Emde-Boas, R. Kass, E. Zijlstra: Design and Implementation of an Efficient Priority Queue. In: Mathematical Systems Theory. 10: 99-127, 1977.
• P. van Emde-Boas: Preserving Order in a Forest in Less than Logarithmic Time and Linear Space. In: Inf. Proc. Letters. 6 (3): 80-82, June 1977.