Abstract

We report on implementation and a modest experimental evaluation of a recently introduced priority-queue data structure. The new data structure is designed to take advantage of fast operations on machine words and, as appropriate, reduced key-universe size and/or tolerance of approximate answers to queries. In addition to standard priority-queue operations, the data structure also supports successor and predecessor queries. Our results suggest that the data structure is practical and can be faster than traditional priority queues when holding a large number of keys, and that tolerance for approximate answers can lead to significant increases in speed.