Min-max heap
Encyclopedia
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.
Double-ended priority queue
A double-ended priority queue is an abstract data type similar to a priority queue except that it allows for efficient removal of both the maximum and minimum element. It is a data structure in which one can insert elements and then remove the elements with minimum or maximum priority. Every...
implemented as a modified version of a binary heap
Binary heap
A binary heap is a heap data structure created using a binary tree. It can be seen as a binary tree with two additional constraints:*The shape property: the tree is a complete binary tree; that is, all levels of the tree, except possibly the last one are fully filled, and, if the last level of...
. 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.