Min-max heap

A min-max heap is a double-ended priority queue implemented as a modified version of a binary heap. Like a binary heap, a min-max heap is represented as a complete binary tree. Unlike a binary heap, though, the nodes in this tree do not obey the min-heap property; rather they obey the min-max heap property. 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.

Like binary heaps, min-max heaps support O(lg n) insertion and deletion, can be built in time O(n), and are often represented implicitly in an array. Operations like findmin() and findmax() take constant time.

References

• Atkinson et al. Min-Max Heaps and Generalized Priority Queues.