The purpose of a min-max ordered heap is to allow us to find both the largest and the smallest element of the heap in constant time, without changing the fact that rebuilding the heap after the removal of an element is done in logarithmic time.
This result is achieved (reference [4]) by a simple change to the heap property. The property is changed into a min-max ordering which specifies the ordering relatively to the two next levels in this way.- A tree is said to be min-max ordered if every element on even (odd) levels are less (greater) than all childrens and grand children. The levels are numbered starting from 1.
Another way to express this ordering is to say that any element on a max-level, i. e. an odd level, is larger than all of its descendants while any element on a min level is less than all of its descendants.
The first formulation of the heap property is well suited as a model for implementing a min-max heap, while the second makes it clearer why the heap works as intended.
The shape property remain unchanged from the basic heap.
It is now obvious that the maximum element in the heap can be found at the root, and that the minimum element is one of the roots two children. Anyway, to rebuild the heap after insertion or deletion of an element is a bit more involved than for the traditional heap.