Queap

A queap is a priority queue data structure that supports insertion of new elements, deletion of arbitrary elements, and retrieval of the element with highest priority, while giving long-lived elements a performance advantage similar to a plain queue. Insertion runs in constant amortized time. Deletion of an element takes amortized time that is logarithmic only in the number of items that have remained in the structure longer than the removed item, rather than in the full size of the structure, so an element inserted recently and removed quickly costs little. Internally a queap combines a doubly linked list, which holds newly inserted elements until a deletion forces them out, with a 2-4 tree; each part tracks its own minimum-priority element so the true minimum can always be found quickly. The structure was devised by John Iacono and Stefan Langerman and published in the journal Algorithmica in 2005.