Queap
Encyclopedia
In computer science
, a queap is a priority queue data structure
that points to the smallest stored item. Queap is composed of a doubly linked list and a 2-4 tree data structure. The data structure satisfies the queueish property, a complement of the working set property, which makes the search operations of some element x to run in O(lgq(x)) amortized time where q(x) is the number of items that has been in the priority queue longer than x.
The doubly linked list keeps a list of k inserted elements. When a deletion operation occurs, the k items are added to the 2-4 tree. The item is then deleted from the tree. Each structure points to the minimum one. The 2-4 tree has been modified for this structure in order to access the smallest element in constant time. The 'queap' was coined by John Iacono and Stefan Langerman
' 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(lgw(x)).
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.
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:
. 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 
, which points to the smallest item in subtree v. Each internal node on path P from the root to 
has a pointer 
, which points to the smallest key in 
. The 
pointers of each internal node on path P are ignored. The queap has a pointer to 
, which points to the smallest element in T.
An application of queap includes a unique set of high priority events and extraction of the highest priority event for processing.
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.
tool. The potential function for queap Q will be
where 
.
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.
and 
pointers may need updating. At most, there will be 
updates.
of some constant a, amortized over the 2-4 tree. After inserting and updating the 
and 
pointers, the total time spent is bounded by 
.
The second operation is to delete x from T, and to walk on the path from x to
, correcting 
and 
values. The time is spent at most 
. If 
, then the amortized cost will be 
.
Delete(Q, x): is the addition of the amortized cost of Minimum(Q) and Delete(Q, x), which is
.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, a queap is a priority queue data structure
Data structure
In computer science, a data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks...
that points to the smallest stored item. Queap is composed of a doubly linked list and a 2-4 tree data structure. The data structure satisfies the queueish property, a complement of the working set property, which makes the search operations of some element x to run in O(lgq(x)) amortized time where q(x) is the number of items that has been in the priority queue longer than x.
The doubly linked list keeps a list of k inserted elements. When a deletion operation occurs, the k items are added to the 2-4 tree. The item is then deleted from the tree. Each structure points to the minimum one. The 2-4 tree has been modified for this structure in order to access the smallest element in constant time. The 'queap' was coined by John Iacono and Stefan Langerman
Description
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 in the heap longer than the element to be extracted. The queap has a property called the queueish property: the time to search for element x is O(lgq(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 xQueap 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.
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:
. 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 , which points to the smallest item in subtree v. Each internal node on path P from the root to has a pointer , which points to the smallest key in . The pointers of each internal node on path P are ignored. The queap has a pointer to , which points to the smallest element in T.An application of queap 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, 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.
- Initialize an empty doubly linked list L and 2-4 tree T. Set k and n to zero.
Insert(Q, x): Add the element x to queap Q.
- Insert the element x in list L. Set the bit in element x to one to demonstrate that the element is in the list L. Update the minL pointer if x is the smallest element in the list. Increment n by 1.
Minimum(Q): Retrieve a pointer to the smallest element from queap Q.
- If key(minL) < key(
), return minL. Otherwise return 
.
Delete(Q, x): Remove element x from queap Q.
- If the bit of the element x is set to one, the element is stored in list L. Add all the elements from L to T, setting the bit of each element to zero. Each element is added to the parent of the right most child of T using the insert operation of the 2-4 tree. L becomes empty. Update
pointers for all the nodes v whose children are new/modified, and repeat the process with the next parent until the parent is equal to the root. Walk from the root to node 
, and update the 
values. Set k equal to n.
- If the bit of the element x is set to zero, x is a leaf of T. Delete x using the 2-4 tree delete operation. Starting from node x, walk in T to node
, updating 
and 
pointers. Decrement n and k by 1.
DeleteMin(Q): Delete and return the smallest element from queap Q.
- Invoke the Minimum(Q) operation. The operation returns min. Invoke the Delete(Q, min) operation. Return min.
CleanUp(Q): Delete all the elements in list L and tree T.
- Starting from the first element in list L, traverse the list, deleting each node.
- Starting from the root of the tree T, traverse the tree using the post-order traversalTree traversalIn computer science, tree-traversal refers to the process of visiting each node in a tree data structure, exactly once, in a systematic way. Such traversals are classified by the order in which the nodes are visited...
algorithm, deleting each node in the tree.
Analysis
The running time is analyzed using the Amortized AnalysisAmortized analysis
In computer science, amortized analysis is a method of analyzing algorithms that considers the entire sequence of operations of the program. It allows for the establishment of a worst-case bound for the performance of an algorithm irrespective of the inputs by looking at all of the operations...
tool. The potential function for queap Q will be
where .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, and pointers may need updating. At most, there will be updates.Case 2
If x is in list L, then all the elements from L are inserted in T. This has a cost of of some constant a, amortized over the 2-4 tree. After inserting and updating the and pointers, the total time spent is bounded by .The second operation is to delete x from T, and to walk on the path from x to
, correcting and values. The time is spent at most . If , then the amortized cost will be .Delete(Q, x): is the addition of the amortized cost of Minimum(Q) and Delete(Q, x), which is
.Code example
A small java implementation of a queap:
public class Queap
{
public int n, k;
public Listl; //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;
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;
}
}
See also
- Queue (data structure)
- Priority queuePriority queueA priority queue is an abstract data type in computer programming.It is exactly like a regular queue or stack data structure, but additionally, each element is associated with a "priority"....
- Splay treeSplay treeA splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O amortized time. For many sequences of nonrandom operations, splay trees perform...
- 2-4 tree
- Doubly linked list
- Amortized analysisAmortized analysisIn computer science, amortized analysis is a method of analyzing algorithms that considers the entire sequence of operations of the program. It allows for the establishment of a worst-case bound for the performance of an algorithm irrespective of the inputs by looking at all of the operations...