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.

Sat Apr 3 18:07:59 METDST 1999