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.
Description.
A queap is a priority queue that inserts elements in O(1) amortized time, and removes the minimum element in O(log("k" + 2)) if there are "k" items that have been in the heap for a longer time than the element to be extracted. The queap has a property called the queueish property: the time to search for element "x" is O(lg "q"("x")) where "q"("x") is equal to "n" − 1 − "w"("x") and "w"("x") is the number of distinct items that has been accessed by operations such as searching, inserting, or deleting. "q"("x") is defined as how many elements have not been accessed since "x"'s last access. Indeed, the queueish property is the complement of the splay tree working set property: the time to search for element "x" is O(lg "w"("x")).
A queap can be represented by two data structures: a doubly linked list and a modified version of 2–4 tree. The doubly linked list, "L", is used for a series of insert and locate-min operations. The queap keeps a pointer to the minimum element stored in the list. To add element "x" to list "l", the element "x" is added to the end of the list and a bit variable in element "x" is set to one. This operation is done to determine if the element is either in the list or in a 2–4 tree. 
A 2–4 tree is used when a delete operation occurs. If the item "x" is already in tree "T", the item is removed using the 2–4 tree delete operation. Otherwise, the item "x" is in list "L" (done by checking if the bit variable is set). All the elements stored in list "L" are then added to the 2–4 tree, setting the bit variable of each element to zero. "x" is then removed from "T". 
A queap uses only the 2–4 tree structure properties, not a search tree. The modified 2–4 tree structure is as follows. Suppose list "L" has the following set of elements: formula_1. When the deletion operation is invoked, the set of elements stored in "L" is then added to the leaves of the 2–4 tree in that order, proceeded by a dummy leaf containing an infinite key. Each internal node of "T" has a pointer formula_2, which points to the smallest item in subtree "v". Each internal node on path "P" from the root to formula_3 has a pointer formula_4, which points to the smallest key in formula_5. The formula_2 pointers of each internal node on path "P" are ignored. The queap has a pointer to formula_7, which points to the smallest element in "T".
An application of queaps includes a unique set of high priority events and extraction of the highest priority event for processing.
Operations.
Let "minL" be a pointer that points to the minimum element in the doubly linked list "L", formula_7 be the minimum element stored in the 2–4 tree, "T", "k" be the number of elements stored in "T", and "n" be the total number of elements stored in queap "Q". The operations are as follows:
New(Q): Initializes a new empty queap.
Insert(Q, x): Add the element "x" to queap "Q".
Minimum(Q): Retrieve a pointer to the smallest element from queap "Q".
Delete(Q, x): Remove element x from queap "Q".
DeleteMin(Q): Delete and return the smallest element from queap "Q".
CleanUp(Q): Delete all the elements in list "L" and tree "T".
Analysis.
The running time is analyzed using the amortized analysis. The potential function for queap Q will be formula_17 where formula_18.
Insert(Q, x): The cost of the operation is "O(1)". The size of list "L" grows by one, the potential increases by some constant "c".
Minimum(Q): The operation does not alter the data structure so the amortized cost is equal to its actual cost, O(1).
Delete(Q, x): There are two cases.
Case 1.
If "x" is in tree "T", then the amortized cost is not modified. The delete operation is "O(1)" amortized 2–4 tree. Since "x" was removed from the tree, formula_2 and formula_4 pointers may need updating. At most, there will be formula_21 updates.
Case 2.
If "x" is in list "L", then all the elements from "L" are inserted in "T". This has a cost of formula_22 of some constant "a", amortized over the 2–4 tree. After inserting and updating the formula_2 and formula_4 pointers, the total time spent is bounded by formula_25. The second operation is to delete "x" from "T", and to walk on the path from x to formula_3, correcting formula_2 and formula_4 values. The time is spent at most formula_29. If formula_30, then the amortized cost will be formula_21.
Delete(Q, x): is the addition of the amortized cost of Minimum(Q) and Delete(Q, x), which is formula_21.
Code example.
A small Java implementation of a queap:
public class Queap
 public int n, k;
 public List<Element> l; // Element is a generic data type.
 public QueapTree t; // a 2-4 tree, modified for Queap purpose
 public Element minL;
 private Queap() {
 n = 0;
 k = 0;
 l = new LinkedList<Element>();
 t = new QueapTree();
 public static Queap New() {
 return new Queap();
 public static void Insert(Queap Q, Element x) {
 if (Q.n == 0)
 Q.minL = x;
 Q.l.add(x);
 x.inList = true;
 if (x.compareTo(Q.minL) < 0)
 Q.minL = x;
 public static Element Minimum(Queap Q) {
 // t is a 2-4 tree and x0, cv are tree nodes.
 if (Q.minL.compareTo(Q.t.x0.cv.key) < 0)
 return Q.minL;
 return Q.t.x0.cv.key;
 public static void Delete(Queap Q, QueapNode x) {
 Q.t.deleteLeaf(x);
 --Q.n;
 --Q.k;
 public static void Delete(Queap Q, Element x) {
 QueapNode n;
 if (x.inList) {
 // set inList of all the elements in the list to false
 n = Q.t.insertList(Q.l, x);
 Q.k = Q.n;
 Delete(Q, n);
 else if ((n = Q.t.x0.cv).key == x)
 Delete(Q, n);
 public static Element DeleteMin(Queap Q) {
 Element min = Minimum(Q);
 Delete(Q, min);
 return min;