Double-ended priority queue
Encyclopedia
A double-ended priority queue (DEPQ) is an abstract data type
similar to a priority queue
except that it allows for efficient removal of both the maximum and minimum element. It is a data structure in which one can insert elements and then remove the elements with minimum or maximum priority. Every element in a DEPQ has a priority or value. In a DEPQ, it is possible to remove the elements in both ascending as well as descending order.
isEmpty: Checks if DEPQ is empty and returns true if empty.
size: Returns the total number of elements preset in the DEPQ.
getMin: Returns the element having least priority.
getMax: Returns the element having highest priority.
put(x): Inserts the element x in the DEPQ.
removeMin: Removes an element with minimum priority and returns this element.
removeMax: Removes an element with maximum priority and returns this element.
If an operation is to be performed on two elements having the same priority, then the element inserted first is chosen. Also, the priority of any element can be changed once it has been inserted in the DEPQ.
and pairing heap
.
Generic methods of arriving at double-ended priority queues from normal priority queues are:
in which each node contains two elements. It is a complete binary tree in which:
Depending on the number of elements, two cases are possible -
The time required for inserting an element depends on the number of movements required to meet all the conditions and is O(log n).
Thus, with interval heaps, both the minimum and maximum elements can be removed efficiently traversing from root to leaf. Thus, a DEPQ can be obtained from an interval heap where the elements of the interval heap are the priorities of elements in the DEPQ.
. In an external sort, there are more elements than can be held in the computer's memory. The elements to be sorted are initially on a disk and the sorted sequence is to be left on the disk. The external quick sort is implemented using the DEPQ as follows:
Abstract data type
In computing, an abstract data type is a mathematical model for a certain class of data structures that have similar behavior; or for certain data types of one or more programming languages that have similar semantics...
similar to a priority queue
Priority queue
A 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"....
except that it allows for efficient removal of both the maximum and minimum element. It is a data structure in which one can insert elements and then remove the elements with minimum or maximum priority. Every element in a DEPQ has a priority or value. In a DEPQ, it is possible to remove the elements in both ascending as well as descending order.
Operations
A double-ended priority queue features the follow operations:isEmpty: Checks if DEPQ is empty and returns true if empty.
size: Returns the total number of elements preset in the DEPQ.
getMin: Returns the element having least priority.
getMax: Returns the element having highest priority.
put(x): Inserts the element x in the DEPQ.
removeMin: Removes an element with minimum priority and returns this element.
removeMax: Removes an element with maximum priority and returns this element.
If an operation is to be performed on two elements having the same priority, then the element inserted first is chosen. Also, the priority of any element can be changed once it has been inserted in the DEPQ.
Implementation
Double-ended priority queues can be built from balanced binary search trees (where the mininum and maximum elements are the leftmost and rightmost leaves, respectively), or using specialized data structures like min-max heapMin-max heap
A min-max heap is a double-ended priority queue implemented as a modified version of a binary heap. Like a binary heap, a min-max heap is represented as a complete binary tree. Unlike a binary heap, though, the nodes in this tree do not obey the min-heap property; rather they obey the min-max heap...
and pairing heap
Pairing heap
A pairing heaps is a type of heap data structure with relatively simple implementation and excellent practical amortized performance. However, it has proven very difficult to determine the precise asymptotic running time of pairing heaps....
.
Generic methods of arriving at double-ended priority queues from normal priority queues are:
Dual structure method
In this method two different priority queues for min and max are maintained. The same elements in both the PQs are shown with the help of correspondence pointers.Total correspondence
Half the elements are in the min PQ and the other half in the max PQ. Each element in the min PQ has a one to one correspondence with an element in max PQ. If the number of elements in the DEPQ is odd, one of the elements is retained in a buffer. Priority of every element in the min PQ will be less than or equal to the corresponding element in the max PQ.Leaf correspondence
In this method only the leaf elements of the min and max PQ form corresponding one to one pairs. It is not necessary for non-leaf elements to be in a one to one correspondence pair.Interval heaps
Apart from the above mentioned correspondence methods, DEPQ's can be obtained efficiently using interval heaps. An interval heap is like an embedded min-max heapMin-max heap
A min-max heap is a double-ended priority queue implemented as a modified version of a binary heap. Like a binary heap, a min-max heap is represented as a complete binary tree. Unlike a binary heap, though, the nodes in this tree do not obey the min-heap property; rather they obey the min-max heap...
in which each node contains two elements. It is a complete binary tree in which:
- The left element is less than or equal to the right element.
- Both the elements define a closed interval.
- Interval represented by any node except the root is a sub-interval of the parent node.
- Elements on the left hand side define a min heap.
- Elements on the right hand side define a max heap.
Depending on the number of elements, two cases are possible -
- Even number of elements: In this case, each node contains two elements say p and q, with p ≤ q. Every node is then represented by the interval [p, q].
- Odd number of elements: In this case, each node except the last contains two elements represented by the interval [p, q] whereas the last node will contain a single element and is represented by the interval [p, p].
Inserting an element
Depending on the number of elements already present in the interval heap, following cases are possible:- Odd number of elements: If the number of elements in the interval heap is odd, the new element is firstly inserted in the last node. Then, it is successively compared with the previous node elements and tested to satisfy the criteria essential for an interval heap as stated above. In case if the element does not satisfy any of the criteria, it is moved from the last node to the root until all the conditions are satisfied.
- Even number of elements: If the number of elements is even, then for the insertion of a new element an additional node is created. If the element falls to the left of the parent interval, it is considered to be in the min heap and if the element falls to the right of the parent interval, it is considered in the max heap. Further, it is compared successively and moved from the last node to the root until all the conditions for interval heap are satisfied. If the element lies within the interval of the parent node itself, the process is stopped then and there itself and moving of elements does not take place.
The time required for inserting an element depends on the number of movements required to meet all the conditions and is O(log n).
Deleting an element
- Min element: In an interval heap, the minimum element is the element on the left hand side of the root node. This element is removed and returned. To fill in the vacancy created on the left hand side of the root node, an element from the last node is removed and reinserted into the root node. This element is then compared successively with all the left hand elements of the descending nodes and the process stops when all the conditions for an interval heap are satisfied.In case if the left hand side element in the node becomes greater than the right side element at any stage, the two elements are swapped and then further comparisons are done. Finally, the root node will again contain the minimum element on the left hand side.
- Max element: In an interval heap, the maximum element is the element on the right hand side of the root node. This element is removed and returned. To fill in the vacancy created on the right hand side of the root node, an element from the last node is removed and reinserted into the root node. Further comparisons are carried out on a similar basis as discussed above. Finally, the root node will again contain the max element on the right hand side.
Thus, with interval heaps, both the minimum and maximum elements can be removed efficiently traversing from root to leaf. Thus, a DEPQ can be obtained from an interval heap where the elements of the interval heap are the priorities of elements in the DEPQ.
Interval Heaps
When DEPQ's are implemented using Interval heaps consisting of n elements, the time complexities for the various functions are formulated in the table below| Operation | Time Complexity |
|---|---|
| init | O(n) |
| isEmpty | O(1) |
| getmin | O(1) |
| getmax | O(1) |
| size | O(1) |
| insert(x) | O(logn) |
| removeMin | O(logn) |
| removeMax | O(logn) |
Pairing heaps
When DEPQ's are implemented using heaps or paring heaps consisting of n elements, the time complexities for the various functions are formulated in the table below. For pairing heaps, it is an amortized complexity.| Operation | Time Complexity |
|---|---|
| isEmpty | O(1) |
| getmin | O(1) |
| getmax | O(1) |
| insert(x) | O(logn) |
| removeMax | O(logn) |
| removeMin | O(logn) |
External sorting
One example application of the double-ended priority queue is external sortingExternal sorting
External sorting is a term for a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted do not fit into the main memory of a computing device and instead they must reside in the slower external memory . External sorting...
. In an external sort, there are more elements than can be held in the computer's memory. The elements to be sorted are initially on a disk and the sorted sequence is to be left on the disk. The external quick sort is implemented using the DEPQ as follows:
- Read in as many elements as will fit into an internal DEPQ. The elements in the DEPQ will eventually be the middle group (pivot) of elements.
- Read in the remaining elements. If the next element is ≤ the smallest element in the DEPQ, output this next element as part of the left group. If the next element is ≥ the largest element in the DEPQ, output this next element as part of the right group. Otherwise, remove either the max or min element from the DEPQ (the choice may be made randomly or alternately); if the max element is removed, output it as part of the right group; otherwise, output the removed element as part of the left group; insert the newly input element into the DEPQ.
- Output the elements in the DEPQ, in sorted order, as the middle group.
- Sort the left and right groups recursively.
Other applications
An airport takeoff and landing system is a practical example of a Double - ended priority queue.- An airplane which wants to take off or land is added to the queue
- Priority may be assigned to the airplane on the basis of parameters like fuel level (while landingLandingthumb|A [[Mute Swan]] alighting. Note the ruffled feathers on top of the wings indicate that the swan is flying at the [[Stall |stall]]ing speed...
) or long distance flights (during takeoffTakeoffTakeoff is the phase of flight in which an aerospace vehicle goes from the ground to flying in the air.For horizontal takeoff aircraft this usually involves starting with a transition from moving along the ground on a runway. For balloons, helicopters and some specialized fixed-wing aircraft , no...
). - The airplane with maximum priority is given the permission to land or take-off first.
See Also
- Queue (ADT)
- 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"....
- Double-ended queue