What is "queap"

In computer science, a queap is a priority queue data structure. The data structure allows insertions and deletions of arbitrary elements, as well as retrieval of the highest-priority element. Each deletion takes amortized time logarithmic in the number of items that have been in the structure for a longer time than the removed item. Insertions take constant amortized time.

The data structure consists of a doubly linked list and a 2-4 tree data structure, each modified to keep track of its minimum-priority element. The basic operation of the structure is to keep newly inserted elements in the doubly linked list, until a deletion would remove one of the list items, at which point they are all moved into the 2-4 tree. The 2-4 tree stores its elements in insertion order, rather than the more conventional priority-sorted order.

Both the data structure and its name were devised by John Iacono and Stefan Langerman.