Min-max heap

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Min-max heap
Type binary tree/heap
Invented 1986
Time complexity in big O notation
Algorithm Average Worst Case
Insert O(log n) O(log n)
Delete O(log n) [1] O(log 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 a double-ended priority queue. Like binary min-heaps and max-heaps, min-max heaps support logarithmic insertion and deletion and can be built in linear time.[3] Min-max heaps are often represented implicitly in an array;[4] hence it's referred to as an implicit data structure.

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 other order-statistics operations efficiently, such as find-median, delete-median,[6]find(k) (determine the kth smallest value in the structure) and the operation delete(k) (delete the kth smallest value in the structure), for any fixed value (or set of values) of k. Specifically, these last two operations can be implemented respectively in constant and logarithmic time. 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.[7] A min-max heap can also be useful when implementing an external quicksort.[8]

Description[edit]

  • 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 level, i.e., 0.
Example of Min-max heap
  • Each node in a min-max heap has a data member (usually called key) whose value is used to determine the order of the node in the min-max heap.
  • 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 be any node in a min-max heap.
    • If is on a min (or even) level, then is the minimum key among all keys in the subtree with root .
    • If is on a max (or odd) level, then is the maximum key among all keys in the subtree with root .
  • A node on a min (max) level is called a min (max) node.

A max-min heap is defined analogously; in such a heap, the maximum value is stored at the root, and the smallest value is stored at one of the root's children.[9]

Operations[edit]

In the following operations we assume that the min-max heap is represented in an array A[1..N]; The location in the array will correspond to a node located on level in the heap.

Build[edit]

Creating a min-max heap is accomplished by an adaption of Floyd's linear-time heap construction algorithm, which proceeds in a bottom-up fashion.[10] A typical Floyd's build-heap algorithm[11] goes as follows:

function FLOYD-BUILD-HEAP (h):
for each index i from down to 1 do:
push-down(h, i) return h

The push-down operation (which sometimes is also called heapify) of a min-max heap is explained next.

Insertion[edit]

To add an element to a min-max heap perform following operations:

  1. Append the required key to the array representing the min-max heap. This will likely break the min-max heap properties, therefore we need to adjust the heap.
  2. 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[edit]

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.

Example of Min-max heap

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. d

Extensions[edit]

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[edit]

  1. ^ Mischel. "Jim". Stack Overflow. Retrieved 8 September 2016. 
  2. ^ ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian, ed. "Min-Max Heaps and Generalized Priority Queues" (PDF). 29: 1. 
  3. ^ ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian, ed. "Min-Max Heaps and Generalized Priority Queues" (PDF). 29: 1, 2. 
  4. ^ ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian, ed. "Min-Max Heaps and Generalized Priority Queues" (PDF). 29: 2. 
  5. ^ ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian, ed. "Min-Max Heaps and Generalized Priority Queues" (PDF). 29: 2. 
  6. ^ ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian, ed. "Min-Max Heaps and Generalized Priority Queues" (PDF). 29: 1. 
  7. ^ ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian, ed. "Min-Max Heaps and Generalized Priority Queues" (PDF). 29: 2. 
  8. ^ https://www.amazon.com/Handbook-Algorithms-Data-Structures-Pascal/dp/0201416077
  9. ^ ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian, ed. "Min-Max Heaps and Generalized Priority Queues" (PDF). 29: 2. 
  10. ^ ATKINSON, M. D; SACK, J.-R; SANTORO, N.; STROTHOTTE, T. (1986). Munro, Ian, ed. "Min-Max Heaps and Generalized Priority Queues" (PDF). 29: 2. 
  11. ^ K. Paparrizos, Ioannis (2011). "A tight bound on the worst-case number of comparisons for Floyd's heap construction algorithm" (PDF).