Min-max heap
Computer data structure
- 9 min read
- 3 chapters
Related on Lably
Through Computer science, Binary tree and 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.
The structure can also be generalized to support other order-statistics operations efficiently, such as find-median, delete-median,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. These last two operations can be implemented in constant and logarithmic time, respectively. 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. A min-max heap can also be useful when implementing an external quicksort.
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 level, i.e., 0.
- 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.
Sign in to keep reading
2 more chapters are free with a Lably account.
Operations
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 the level in the heap.
Build
Creating a min-max heap is accomplished by an adaptation of Floyd's linear-time heap construction algorithm, which proceeds in a bottom-up fashion. A typical Floyd's build-heap algorithm goes as follows:
<b id="mwcw">function FLOYD-BUILD-HEAP</b>(<i id="mwdA">h</i>): <b id="mwdQ">for</b> each index <i id="mwdg">i</i> from <span class="mwe-math-element mwe-math-element-inline" typeof="mw:Extension/math" about="#mwt40" data-mw='{"name":"math","attrs":{},"body":{"extsrc":"\\lfloor length(h) / 2 \\rfloor"}}' id="mwdw"><span class="mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" class="mathjax_ignore" alttext="{\displaystyle \lfloor length(h)/2\rfloor }"> <semantics> <mrow class="MJX-TeXAtom-ORD"> <mstyle displaystyle="true" scriptlevel="0"> <mo fence="false" stretchy="false">⌊<!-- ⌊ --></mo> <mi>l</mi> <mi>e</mi> <mi>n</mi> <mi>g</mi> <mi>t</mi> <mi>h</mi> <mo stretchy="false">(</mo> <mi>h</mi> <mo stretchy="false">)</mo> <mrow class="MJX-TeXAtom-ORD"> <mo>/</mo> </mrow> <mn>2</mn> <mo fence="false" stretchy="false">⌋<!-- ⌋ --></mo> </mstyle> </mrow> <annotation encoding="application/x-tex">{\displaystyle \lfloor length(h)/2\rfloor }</annotation> </semantics> </math></span><img src="https://wikimedia.org/api/rest_v1/media/math/render/svg/1af0f7730d5edeb28b77a3f0aeb1daf1f627e2ef" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.004ex; height:2.843ex;" alt="{\displaystyle \lfloor length(h)/2\rfloor }"/></span><b id="mweA">down to</b> 1 <b id="mweQ">do:</b> <b id="mweg">push-down</b>(<i id="mwew">h</i>, <i id="mwfA">i</i>) <b id="mwfQ">return</b> hIn this function, h is the initial array, whose elements may not be ordered according to the min-max heap property. The push-down operation (which sometimes is also called heapify) of a min-max heap is explained next.
Push Down
The push-down algorithm (or trickle-down as it is called in ) is as follows:
<b id="mwiw">function PUSH-DOWN</b>(<i id="mwjA">h</i>, <i id="mwjQ">i</i>): <b id="mwjg">if</b> <i id="mwjw">i</i> is on a min level <b id="mwkA">then:</b> <b id="mwkQ">PUSH-DOWN-MIN</b>(<i id="mwkg">h</i>, <i id="mwkw">i</i>) <b id="mwlA">else:</b> <b id="mwlQ">PUSH-DOWN-MAX(</b><i id="mwlg">h</i>, <i id="mwlw">i</i>) <b id="mwmA">endif</b>
Push Down Min
<b id="mwmw">function PUSH-DOWN-MIN</b>(<i id="mwnA">h</i>, <i id="mwnQ">i</i>): <b id="mwng">if</b> <i id="mwnw">i</i> has children <b id="mwoA">then:</b> <i id="mwoQ">m</i> := index of the smallest child or grandchild of <i id="mwog">i</i> <b id="mwow">if</b> <i id="mwpA">m</i> is a grandchild of <i id="mwpQ">i</i> <b id="mwpg">then:</b> <b id="mwpw">if</b> <i id="mwqA">h[m]</i> < <i id="mwqQ">h[i]</i> <b id="mwqg">then:</b> swap <i id="mwqw">h[m]</i> and <i id="mwrA">h[i]</i> <b id="mwrQ">if</b> <i id="mwrg">h[m]</i> > <i id="mwrw">h[parent(m)]</i> <b id="mwsA">then:</b> swap <i id="mwsQ">h[m]</i> and <i id="mwsg">h[parent(m)]</i> <b id="mwsw">endif</b> <b id="mwtA">PUSH-DOWN</b>(<i id="mwtQ">h</i>, <i id="mwtg">m</i>) <b id="mwtw">endif</b> <b id="mwuA">else if</b> <i id="mwuQ">h[m]</i> < <i id="mwug">h[i]</i> <b id="mwuw">then:</b> swap <i id="mwvA">h[m]</i> and <i id="mwvQ">h[i]</i> <b id="mwvg">endif</b> <b id="mwvw">endif</b>
Push Down Max
The algorithm for push-down-max is identical to that for push-down-min, but with all of the comparison operators reversed.
<b id="mwxA">function PUSH-DOWN-MAX</b>(<i id="mwxQ">h</i>, <i id="mwxg">i</i>): <b id="mwxw">if</b> <i id="mwyA">i</i> has children <b id="mwyQ">then:</b> <i id="mwyg">m</i> := index of the largest child or grandchild of <i id="mwyw">i</i> <b id="mwzA">if</b> <i id="mwzQ">m</i> is a grandchild of <i id="mwzg">i</i> <b id="mwzw">then:</b> <b id="mw0A">if</b> <i id="mw0Q">h[m]</i> > <i id="mw0g">h[i]</i> <b id="mw0w">then:</b> swap <i id="mw1A">h[m]</i> and <i id="mw1Q">h[i]</i> <b id="mw1g">if</b> <i id="mw1w">h[m]</i> < <i id="mw2A">h[parent(m)]</i> <b id="mw2Q">then:</b> swap <i id="mw2g">h[m]</i> and <i id="mw2w">h[parent(m)]</i> <b id="mw3A">endif</b> <b id="mw3Q">PUSH-DOWN</b>(<i id="mw3g">h</i>, <i id="mw3w">m</i>) <b id="mw4A">endif</b> <b id="mw4Q">else if</b> <i id="mw4g">h[m]</i> > <i id="mw4w">h[i]</i> <b id="mw5A">then:</b> swap <i id="mw5Q">h[m]</i> and <i id="mw5g">h[i]</i> <b id="mw5w">endif</b> <b id="mw6A">endif</b>
Iterative Form
As the recursive calls in push-down-min and push-down-max are in tail position, these functions can be trivially converted to purely iterative forms executing in constant space:
<b id="mw7g">function PUSH-DOWN-ITER</b>(<i id="mw7w">h</i>, <i id="mw8A">m</i>): <b id="mw8Q">while</b> <i id="mw8g">m</i> has children <b id="mw8w">then:</b> <i id="mw9A">i := m</i> <b id="mw9Q">if</b> <i id="mw9g">i</i> is on a min level <b id="mw9w">then:</b> <i id="mw-A">m</i> := index of the smallest child or grandchild of <i id="mw-Q">i</i> <b id="mw-g">if</b> <i id="mw-w">h[m]</i> < <i id="mw_A">h[i]</i> <b id="mw_Q">then:</b> swap <i id="mw_g">h[m]</i> and <i id="mw_w">h[i]</i> <b id="mwAQA">if</b> <i id="mwAQE">m</i> is a grandchild of <i id="mwAQI">i</i> <b id="mwAQM">then:</b> <b id="mwAQQ">if</b> <i id="mwAQU">h[m]</i> > <i id="mwAQY">h[parent(m)]</i> <b id="mwAQc">then:</b> swap <i id="mwAQg">h[m]</i> and <i id="mwAQk">h[parent(m)]</i> <b id="mwAQo">endif</b> <b id="mwAQs">else</b> break <b id="mwAQw">endif</b> <b id="mwAQ0">else</b> break <b id="mwAQ4">endif</b> <b id="mwAQ8">else:</b> <i id="mwARA">m</i> := index of the largest child or grandchild of <i id="mwARE">i</i> <b id="mwARI">if</b> <i id="mwARM">h[m]</i> > <i id="mwARQ">h[i]</i> <b id="mwARU">then:</b> swap <i id="mwARY">h[m]</i> and <i id="mwARc">h[i]</i> <b id="mwARg">if</b> <i id="mwARk">m</i> is a grandchild of <i id="mwARo">i</i> <b id="mwARs">then:</b> <b id="mwARw">if</b> <i id="mwAR0">h[m]</i> < <i id="mwAR4">h[parent(m)]</i> <b id="mwAR8">then:</b> swap <i id="mwASA">h[m]</i> and <i id="mwASE">h[parent(m)]</i> <b id="mwASI">endif</b> <b id="mwASM">else</b> break <b id="mwASQ">endif</b> <b id="mwASU">else</b> break <b id="mwASY">endif</b> <b id="mwASc">endif</b> <b id="mwASg">endwhile</b>
Insertion
To add an element to a min-max heap perform following operations:
- Append the required key to (the end of) the array representing the min-max heap. This will likely break the min-max heap properties, therefore we need to adjust the heap.
- Compare the new key to its parent:
- If it is found to be less (greater) than the parent, then it is surely less (greater) than all other nodes on max (min) levels that are on the path to the root of heap. Now, just check for nodes on min (max) levels.
- The path from the new node to the root (considering only min (max) levels) should be in a descending (ascending) order as it was before the insertion. So, we need to make a binary insertion of the new node into this sequence. Technically it is simpler to swap the new node with its parent while the parent is greater (less).
This process is implemented by calling the push-up algorithm described below on the index of the newly-appended key.
Push Up
The push-up algorithm (or bubble-up as it is called in ) is as follows:
<b id="mwATw">function PUSH-UP</b>(<i id="mwAT0">h</i>, <i id="mwAT4">i</i>): <b id="mwAT8">if</b> <i id="mwAUA">i</i> is not the root <b id="mwAUE">then:</b> <b id="mwAUI">if</b> <i id="mwAUM">i</i> is on a min level <b id="mwAUQ">then:</b> <b id="mwAUU">if</b> <i id="mwAUY">h[i] > h[parent(i)]</i> <b id="mwAUc">then:</b> swap <i id="mwAUg">h[i]</i> and <i id="mwAUk">h[parent(i)]</i> <b id="mwAUo">PUSH-UP-MAX</b>(<i id="mwAUs">h, parent(i)</i>) <b id="mwAUw">else:</b> <b id="mwAU0">PUSH-UP-MIN</b>(<i id="mwAU4">h</i>, <i id="mwAU8">i</i>) <b id="mwAVA">endif</b> <b id="mwAVE">else:</b> <b id="mwAVI">if</b> <i id="mwAVM">h[i] < h[parent(i)]</i> <b id="mwAVQ">then:</b> swap <i id="mwAVU">h[i]</i> and <i id="mwAVY">h[parent(i)]</i> <b id="mwAVc">PUSH-UP-MIN</b>(<i id="mwAVg">h, parent(i)</i>) <b id="mwAVk">else:</b> <b id="mwAVo">PUSH-UP-MAX</b>(<i id="mwAVs">h</i>, <i id="mwAVw">i</i>) <b id="mwAV0">endif</b> <b id="mwAV4">endif</b> <b id="mwAV8">endif</b>
Push Up Min
<b id="mwAWI">function PUSH-UP-MIN</b>(<i id="mwAWM">h</i>, <i id="mwAWQ">i</i>): <b id="mwAWU">if</b> <i id="mwAWY">i</i> has a grandparent <b id="mwAWc">and</b> <i id="mwAWg">h[i] < h[grandparent(i)]</i> <b id="mwAWk">then:</b> swap <i id="mwAWo">h[i]</i> and <i id="mwAWs">h[grandparent(i)]</i> <b id="mwAWw">PUSH-UP-MIN</b>(<i id="mwAW0">h, grandparent(i)</i>) <b id="mwAW4">endif</b>
Push Up Max
As with the push-down operations, push-up-max is identical to push-up-min, but with comparison operators reversed:
<b id="mwAXU">function PUSH-UP-MAX</b>(<i id="mwAXY">h</i>, <i id="mwAXc">i</i>): <b id="mwAXg">if</b> <i id="mwAXk">i</i> has a grandparent <b id="mwAXo">and</b> <i id="mwAXs">h[i] > h[grandparent(i)]</i> <b id="mwAXw">then:</b> swap <i id="mwAX0">h[i]</i> and <i id="mwAX4">h[grandparent(i)]</i> <b id="mwAX8">PUSH-UP-MAX</b>(<i id="mwAYA">h, grandparent(i)</i>) <b id="mwAYE">endif</b>
Iterative Form
As the recursive calls to push-up-min and push-up-max are in tail position, these functions also can be trivially converted to purely iterative forms executing in constant space:
<b id="mwAYc">function PUSH-UP-MIN-ITER</b>(<i id="mwAYg">h</i>, <i id="mwAYk">i</i>): <b id="mwAYo">while</b> <i id="mwAYs">i</i> has a grandparent <b id="mwAYw">and</b> <i id="mwAY0">h[i] < h[grandparent(i)]</i> <b id="mwAY4">then:</b> swap <i id="mwAY8">h[i]</i> and <i id="mwAZA">h[grandparent(i)]</i> <i id="mwAZE">i</i> := <i id="mwAZI">grandparent(i)</i> <b id="mwAZM">endwhile</b>
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 insert a new node with value 6.
Initially, node 6 is inserted as a right child of the node 11. 6 is less than 11, therefore it is less than all the nodes on the max levels (41), and we need to check only the min levels (8 and 11). We should swap the nodes 6 and 11 and then swap 6 and 8. So, 6 gets moved to the root position of the heap, the former root 8 gets moved down to replace 11, and 11 becomes a right child of 8.
Consider adding the new node 81 instead of 6. Initially, the node is inserted as a right child of the node 11. 81 is greater than 11, therefore it is greater than any node on any of the min levels (8 and 11). Now, we only need to check the nodes on the max levels (41) and make one swap.
Find Minimum
The minimum node (or a minimum node in the case of duplicate keys) of a Min-Max Heap is always located at the root. Find Minimum is thus a trivial constant time operation which simply returns the roots.
Find Maximum
The maximum node (or a maximum node in the case of duplicate keys) of a Min-Max Heap that contains more than one node is always located on the first max level--i.e., as one of the immediate children of the root. Find Maximum thus requires at most one comparison, to determine which of the two children of the root is larger, and as such is also a constant time operation. If the Min-Max heap contains one node then that node is the maximum node.
Remove Minimum
Removing the minimum is just a special case of removing an arbitrary node whose index in the array is known. In this case, the last element of the array is removed (reducing the length of the array) and used to replace the root, at the head of the array. push-down is then called on the root index to restore the heap property in time.
Remove Maximum
Removing the maximum is again a special case of removing an arbitrary node with known index. As in the Find Maximum operation, a single comparison is required to identify the maximal child of the root, after which it is replaced with the final element of the array and push-down is then called on the index of the replaced maximum to restore the heap property.
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.