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 find-median, delete-median,find(k) (determine the kth smallest value in the structure) and the operation delete(k) (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 min-max heap is a complete binary tree containing alternating min (or even) and max (or odd) levels. Even levels are for example 0, 2, 4, etc, and odd levels are respectively 1, 3, 5, etc. We assume in the next points that the root element is at the first level, i.e., 0.
Each node in a min-max heap has a data member (usually called key) whose value is used to determine the order of the node in the min-max heap. The root element is the smallest element in the min-max heap. One of the two elements in the second level, which is a max (or odd) level, is the greatest element in the min-max heap Let x {\displaystyle x} be any node in a min-max heap. If x {\displaystyle x} is on a min (or even) level, then x . k e y {\displaystyle x.key} is the minimum key among all keys in the subtree with root x {\displaystyle x} . If x {\displaystyle x} is on a max (or odd) level, then x . k e y {\displaystyle x.key} is the maximum key among all keys in the subtree with root x {\displaystyle x} . A node on a min (max) level is called a min (max) node. 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 A[1..N]; The i t h {\displaystyle ith} location in the array will correspond to a node located on the level ⌊ log 2 i ⌋ {\displaystyle \lfloor \log _{2}i\rfloor } in the heap.
Build Creating a min-max heap is accomplished by an adaptation 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 ⌊ l e n g t h ( h ) / 2 ⌋ {\displaystyle \lfloor length(h)/2\rfloor } down 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 push-down operation (which sometimes is also called heapify) of a min-max heap is explained next.
Push Down The push-down algorithm (or trickle-down 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(h, m) endif else if h[m] < h[i] then: swap h[m] and h[i] endif endif
Push Down Max The algorithm for push-down-max 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(h, m) endif else if h[m] > h[i] then: swap h[m] and h[i] endif endif
Iterative Form As the recursive calls in push-down-min and push-down-max are in tail position, these functions can be trivially converted to purely iterative forms executing in constant space:
… excerpt ends here. Continue reading the full article.
