Queap information

This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources. Find sources: "Queap" – news · newspapers · books · scholar · JSTOR (April 2013)

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.^[1]