Min-max heap

In computer science, a "min-max heap" is a complete binary tree data structure which combines the usefulness of both a min-heap and a max-heap, that is, it provides constant time retrieval and logarithmic time removal of both the minimum and maximum elements in it. This makes the min-max heap a very useful data structure to implement a double-ended priority queue. Like binary min-heaps and max-heaps, min-max heaps support logarithmic insertion and deletion and can be built in linear time. Min-max heaps are often represented implicitly in an "array"; hence it's referred to as an implicit data structure.
The "min-max heap" property is: "each node at an even level in the tree is less than all of its descendants, while each node at an odd level in the tree is greater than all of its descendants".
The structure can also be generalized to support other order-statistics operations efficiently, such as codice_1, codice_2,codice_3 (determine the "kth" smallest value in the structure) and the operation codice_4 (delete the "kth" smallest value in the structure), for any fixed value (or set of values) of "k". These last two operations can be implemented in constant and logarithmic time, respectively. The notion of min-max ordering can be extended to other structures based on the max- or min-ordering, such as leftist trees, generating a new (and more powerful) class of data structures. A min-max heap can also be useful when implementing an external quicksort.
Description.
A "max-min heap" is defined analogously; in such a heap, the maximum value is stored at the root, and the smallest value is stored at one of the root's children.
Operations.
In the following operations we assume that the min-max heap is represented in an array codice_5; The formula_8 location in the array will correspond to a node located on the level formula_9 in the heap.
Build.
Creating a min-max heap is accomplished by an adaption of Floyd's linear-time heap construction algorithm, which proceeds in a bottom-up fashion. A typical Floyd's "build-heap" algorithm goes as follows:
 function FLOYD-BUILD-HEAP("h"):
 for each index "i" from formula_10down to 1 do:
 push-down("h", "i")
 return h
In this function, "h" is the initial array, whose elements may not be ordered according to the min-max heap property. The codice_6 operation (which sometimes is also called "heapify") of a min-max heap is explained next.
Push Down.
The codice_6 algorithm (or codice_8 as it is called in 
) is as follows:
 function PUSH-DOWN("h", "i"):
 if "i" is on a min level then:
 PUSH-DOWN-MIN("h", "i")
 else:
 PUSH-DOWN-MAX("h", "i")
 endif
Push Down Min.
 function PUSH-DOWN-MIN("h", "i"):
 if "i" has children then:
 "m" := index of the smallest child or grandchild of "i"
 if" "m" is a grandchild of "i" then:
 if "h[m]" < "h[i]" then:
 swap "h[m]" and "h[i]"
 if "h[m]" > "h[parent(m)]" then:
 swap "h[m]" and "h[parent(m)]"
 endif
 PUSH-DOWN-MIN("h", "m")
 endif
 else if "h[m]" < "h[i]" then:
 swap "h[m]" and "h[i]"
 endif 
 endif
Push Down Max.
The algorithm for codice_9 is identical to that for push-down-min, but with all of the comparison operators reversed.
 function PUSH-DOWN-MAX("h", "i"):
 if "i" has children then:
 "m" := index of the largest child or grandchild of "i"
 if "m" is a grandchild of "i" then:
 if "h[m]" > "h[i]" then:
 swap "h[m]" and "h[i]"
 if "h[m]" < "h[parent(m)]" then:
 swap "h[m]" and "h[parent(m)]"
 endif
 PUSH-DOWN-MAX("h", "m")
 endif
 else if "h[m]" > "h[i]" then:
 swap "h[m]" and "h[i]"
 endif 
 endif
Iterative Form.
As the recursive calls to codice_10 and codice_9 are in tail position, these functions can be trivially converted to purely iterative forms executing in constant space:
 function PUSH-DOWN-MIN-ITER("h", "m"):
 while "m" has children then:
 "i := m"
 "m" := index of the smallest child or grandchild of "i"
 if "h[m]" < "h[i]" then:
 if "m" is a grandchild of "i" then:
 swap "h[m]" and "h[i]"
 if "h[m]" > "h[parent(m)]" then:
 swap "h[m]" and "h[parent(m)]"
 endif
 else
 swap "h[m]" and "h[i]"
 endif
 else
 break 
 endif 
 endwhile
Insertion.
To add an element to a min-max heap perform following operations:
This process is implemented by calling the codice_12 algorithm described below on the index of the newly-appended key.
Push Up.
The codice_12 algorithm (or codice_14 as it is called in 
) is as follows:
 function PUSH-UP("h", "i"):
 if "i" is not the root then:
 if "i" is on a min level then:
 if "h[i] > h[parent(i)]" then:
 swap "h[i]" and "h[parent(i)]"
 PUSH-UP-MAX("h, parent(i)")
 else:
 PUSH-UP-MIN("h", "i")
 endif
 else:
 if "h[i] < h[parent(i)]" then:
 swap "h[i]" and "h[parent(i)]"
 PUSH-UP-MIN("h, parent(i)")
 else:
 PUSH-UP-MAX("h", "i")
 endif
 endif
 endif
Push Up Min.
 function PUSH-UP-MIN("h", "i"):
 if "i" has a grandparent and "h[i] < h[grandparent(i)]" then:
 swap "h[i]" and "h[grandparent(i)]"
 PUSH-UP-MIN("h, grandparent(i)")
 endif
Push Up Max.
As with the codice_6 operations, codice_16 is identical to codice_17, but with comparison operators reversed:
 function PUSH-UP-MAX("h", "i"):
 if "i" has a grandparent and "h[i] > h[grandparent(i)]" then:
 swap "h[i]" and "h[grandparent(i)]"
 PUSH-UP-MAX("h, grandparent(i)")
 endif
Iterative Form.
As the recursive calls to codice_17 and codice_16 are in tail position, these functions also can be trivially converted to purely iterative forms executing in constant space:
 function PUSH-UP-MIN-ITER("h", "i"):
 while "i" has a grandparent and "h[i] < h[grandparent(i)]" then:
 swap "h[i]" and "h[grandparent(i)]"
 "i" := "grandparent(i)"
 endwhile
Example.
Here is one example for inserting an element to a Min-Max Heap.
Say we have the following min-max heap and want to insert a new node with value 6.
Initially, node 6 is inserted as a right child of the node 11. 6 is less than 11, therefore it is less than all the nodes on the max levels (41), and we need to check only the min levels (8 and 11). We should swap the nodes 6 and 11 and then swap 6 and 8. So, 6 gets moved to the root position of the heap, the former root 8 gets moved down to replace 11, and 11 becomes a right child of 8.
Consider adding the new node 81 instead of 6. Initially, the node is inserted as a right child of the node 11. 81 is greater than 11, therefore it is greater than any node on any of the min levels (8 and 11). Now, we only need to check the nodes on the max levels (41) and make one swap.
Find Minimum.
The minimum node (or a minimum node in the case of duplicate keys) of a Min-Max Heap is always located at the root. Find Minimum is thus a trivial constant time operation which simply returns the roots.
Find Maximum.
The maximum node (or a maximum node in the case of duplicate keys) of a Min-Max Heap is always located on the first max level--i.e., as one of the immediate children of the root. Find Maximum thus requires at most one comparison, to determine which of the two children of the root is larger, and as such is also a constant time operation.
Remove Minimum.
Removing the minimum is just a special case of removing an arbitrary node whose index in the array is known. In this case, the last element of the array is removed (reducing the length of the array) and used to replace the root, at the head of the array. codice_6 is then called on the root index to restore the heap property in formula_11time.
Remove Maximum.
Removing the maximum is again a special case of removing an arbitrary node with known index. As in the Find Maximum operation, a single comparison is required to identify the maximal child of the root, after which it is replaced with the final element of the array and codice_6 is then called on the index of the replaced maximum to restore the heap property.
Extensions.
The min-max-median heap is a variant of the min-max heap, suggested in the original publication on the structure, that supports the operations of an order statistic tree.