Min-max heap

Min-max heap
Type	binary tree/heap
Invented	1986
Time complexity in big O notation
	Average	Worst case
Space
Search
Insert	$O(log 2 n)$	$O(log 2 n)$
Delete	$O(log 2 n)$ ^[1]	$O(log 2 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.^[2] This makes the min-max heap a very useful data structure to implement double-ended priority queue. Like binary min-heaps and max-heaps, min-max heaps support $O(\log _{2}n)$ insertion and deletion, can be built in time $O(n)$ ,^[3] and are often represented implicitly in an array.^[4]

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.^[5]

The structure can also be generalized to support the operation find(k) (determine the kth smallest value in the structure) in constant time and the operation delete(k) (delete the kth smallest value in the structure) in logarithmic time, for any fixed value (or set of values) of k. 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.^[6]

Description

A min-max heap is a complete binary tree containing alternating min (or even) and max (or odd) levels. Even levels are for example 0, 2, 4, etc, and odd levels are respectively 1, 3, 5, etc. We assume in the next points that the root element is at the first even level (0).

Example of Min-max heap

Each node in a min-max heap has a data member usually called key
The root element is the smallest element in the min-max heap
One of the two elements in the second level, which is a max (or odd) level, is the greatest element in the min-max heap
Let $x$ be any node in a min-max heap.
- If $x$ is on a min (or even) level then the element in $x$ has the minimum key from among all elements in the subtree with root $x$ .
- If $x$ is on a max (or odd) level then the element in $x$ has the maximum key from among all elements in the subtree with root $x$ .
A node on a min (max) level is called a min (max) node.

Operations

Inserting an element (with an arbitrary key)

To add an element to a Min-Max Heap perform following operations:

Insert the required key into given Min-Max Heap.
Compare this key with its parent.
1. If it is found to be smaller (greater) compared to its parent, then it is surely smaller (greater) than all other keys present at nodes at max(min) level that are on the path from the present position of key to the root of heap. Now, just check for nodes on Min(Max) levels.
2. If the key added is in correct order then stop otherwise swap that key with its parent.

Example

Here is one example for inserting an element to a Min-Max Heap.

Say we have the following min-max heap and want to install a new node with value 6.

Initially, element 6 is inserted at the position indicated by j. Element 6 is less than its parent element. Hence it is smaller than all max levels and we only need to check the min levels. Thus, element 6 gets moved to the root position of the heap and the former root, element 8, gets moved down one step.

If we want to insert a new node with value 81 in the given heap, we advance similarly. Initially the node is inserted at the position j. Since element 81 is larger than its parent element and the parent element is at min level, it is larger than all elements that are on min levels. Now we only need to check the nodes on max levels.

Find the minimum element

Find the maximum element

Delete the minimum element

To delete min element from a Min-Max Heap perform following operations.

The smallest element is the root element.

Remove the root node and the node which is at the end of heap. Let it be x.
Reinsert key of x into the min-max heap

Reinsertion may have 2 cases:

If root has no children, then x can be inserted into the root.
Suppose root has at least one child. Find minimum value ( Let this is be node m). m is in one of the children or grandchildren of the root. The following condition must be considered:
1. x.key <= h[m].key: x must be inserted into the root.
2. x.key > h[m].key and m is child of the root L: Since m is in max level, it has no descendants. So, the element h[m] is moved to the root and x is inserted into node m.
3. x.key > h[m].key and m is grandchild of the root: So, the element h[m] is moved to the root. Let p be parent of m. if x.key > h[p].key then h[p] and x are interchanged.

Program - to delete the element with minimum key

element del_min(element heap[], int *s) { // *s: capacity of the heap
    int i, last, m, parent;
    element temp, x;
    
    if ((*s) == 0) {
        heap[0].key = INT_MAX;        
        return(heap[0]);
    }
    
    heap[0] = heap[1];
    x = heap[(*s)--];
    
    /* find place to insert x */
    for (i = 1, last = (*s) / 2; i <= last;  ) {
        m = min_child_grandchild(i, *s);
        
        if (x.key <= heap[m].key) // case 1
            break;
        
        heap[i] = heap[m]; // case 2 or 3
        
        if (m <= (2 * i) + 1) { // case 2
            i = m;            
            break;
        }
        
        /* case 3 */
        parent = m / 2;
        
        if (x.key > heap[parent].key)
            SWAP(heap[parent], x, temp);
        
        i = m;
    }
    
    heap[i] = x;    
    return heap[0];
}

Delete the maximum element

Extensions

The min-max-median heap is a variant of the min-max heap, suggested in the original publication on the structure, that supports the operations of an order statistic tree.

References

↑ Mischel. "Jim". Stack Overflow. Retrieved 8 September 2016.
↑ ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian, ed. "Min-Max Heaps and Generalized Priority Queues" (PDF). Min-Max Heaps and Generalized Priority Queues. 29: 1.
↑ ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian, ed. "Min-Max Heaps and Generalized Priority Queues" (PDF). Min-Max Heaps and Generalized Priority Queues. 29: 1, 2.
↑ ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian, ed. "Min-Max Heaps and Generalized Priority Queues" (PDF). Min-Max Heaps and Generalized Priority Queues. 29: 2.
↑ ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian, ed. "Min-Max Heaps and Generalized Priority Queues" (PDF). Min-Max Heaps and Generalized Priority Queues. 29: 2.
↑ ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian, ed. "Min-Max Heaps and Generalized Priority Queues" (PDF). Min-Max Heaps and Generalized Priority Queues. 29: 2.

M. D. Atkinson, J.R. Sack, N. Santoro, and T. Strothotte, Communications of the ACM, October, 1986, Min-Max Heaps and Generalized Priority Queues.

This article is issued from Wikipedia - version of the 9/9/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.