Min-max heap
| Min-max heap | |||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Type | binary tree/heap | ||||||||||||
| Invented | 1986 | ||||||||||||
| Time complexity in big O notation | |||||||||||||
|
|||||||||||||
| Algorithm | Average | Worst Case | |
|---|---|---|---|
| Insert | O(log n) | O(log n) | |
| Delete | O(log n) | O(log n) |
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. Specifically, these last two operations can be implemented respectively in constant and logarithmic time. 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.
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.
In the following operations we assume that the min-max heap is represented in an array A[1..N]; The location in the array will correspond to a node located on level in the heap.
...
Wikipedia