Antoun J. Yaacoub Ph.D.

A $\texttt{Min-Max Heap}$ is a hybrid data structure between a $\texttt{Min Heap}$ and a $\texttt{Max Heap}$. More precisely, it is a perfect $\texttt{BT}$ in which:

nodes on an even level are smaller than those of their descendants (direct or indirect) and,
nodes on an odd level are greater than those of their descendants (direct or indirect).

Note that the root has forcibly the minimum value of the heap, and the maximum value is one of the two children of the root (or the root itself if it has no children).

The tree is perfect, it will be represented and manipulated as a sort on array:

$\begin{array}{| c |c |c |c |c |c |c |c |c |c |c |c |c |c |c |c |c |c |c |c| } \hline 5 & 65 & 80 & 25 & 37 & 8 & 15 & 57 & 36 & 45 & 59 & 20 & 14 & 42 & 18 & 28 & 30 & 34 & 27 & 39 \\ \hline \end{array}$

The children of a node of index i are found on positions $\texttt{LeftChild(i)}$ (i.e. $2*i+1$) and $\texttt{RightChild(i)}$ (i.e. $2*i+2$) if it exist. The parent is at position $Parent(i)$ (i.e. $\frac{i-1}{2}$)

Write the function $\texttt{IsOnMinLevel(A,i)}$ that decides in constant time if the index $i$ corresponds to a node located on an even level (or level "min") of a Min-Max heap represented by the array $A$.

The functions on the min-max heap are similar to the functions of a max heap being seen in course.

The $\texttt{PercolateDown(A, i)}$ function, takes a node of index $i$ in which the two subtrees satisfy the heap property, and brings down the value of $A[i]$ in one of the sub-trees so that the property of the heap is checked from the index $i$. In the case of a min-max heap, this function is required to distinguish between the min and max levels as follows:

void PercolateDown(Heap *h, int i){ if(isOnMinLevel(*h,i)) PercolateDownMin(h,i); else PercolateDownMax(h,i);}void PercolateDownMin(Heap *h, int i){ int lc, rc, lgc,rgc, min, temp; lc = LeftChild(*h,i); rc = RightChild(*h,i); // if (*h)->array[i] has children then, // put in min the index of the smallest of the children // and grandchildren (if any) of (*h)->array[i] if(lc!=-1 && (*h)->array[lc]<(*h)->array[i]) min = lc; else min = i; if(lc!=-1) { lgc= LeftChild(*h,lc); rgc = RightChild(*h,lc); if(lgc!=-1 && (*h)->array[lgc]<(*h)->array[min]) min = lgc; if(rgc!=-1 && (*h)->array[rgc]<(*h)->array[min]) min = rgc; } if(rc!=-1 && (*h)->array[rc]<(*h)->array[min]) min = rc; if(rc!=-1) { lgc= LeftChild(*h,rc); rgc = RightChild(*h,rc); if(lgc!=-1 && (*h)->array[lgc]<(*h)->array[min]) min = lgc; if(rgc!=-1 && (*h)->array[rgc]<(*h)->array[min]) min = rgc; } if(min != i) { temp = (*h)->array[i]; (*h)->array[i]= (*h)->array[min]; (*h)->array[min]=temp; if(grandchild(min,i)) if((*h)->array[min] > (*h)->array[Parent(min)]) { temp = (*h)->array[min]; (*h)->array[min]= (*h)->array[Parent(min)]; (*h)->array[Parent(min)]=temp; PercolateDownMin(h,min); } }}

The function $\texttt{PercolateDownMax}$ is similar to $\texttt{PercolateDownMin}$ by changing the sign of the comparisons and defining $max$ as the index of the greatest child and children.

Give the worst case complexity of $\texttt{PercolateDown}$ based on the number $\texttt{n}$ of values in the array. Explain your answer.

Removing the smallest value (root) or the highest value (one of the root children if it exist) of a min-max heap is done like on conventional heap by replacing this value by the last one of the array (which reduces the size of the heap of 1) and by calling $\texttt{PercolateDown}$ on the node whose value has been changed.

Write the function $\texttt{DeleteMax(Heap *h)}$ which removes the maximum value of the min-max heap. You can assume that this function is never called on a empty array
Give the complexity of the previous function in terms on the size $\texttt{n}$ of the array.
Give the content of the array shown in the example after two calls for $\texttt{DeleteMax}$.

Difficulty level

This exercise is mostly suitable for students

1)
int IsOnMinLevel(int A[], int i)
{
	return floor(log(i+1)/log(2)) %2 == 1;
}

2) O(log(n))

3) 
void DeleteMax(Heap *h)
{
	int m;
	if((*h)->count==1)
		(*h)->count=0;
	else
	{
		if((*h)->count>=2 && (*h)->array[2]> (*h)->array[1])
			m=2;
		else
			m=1;
		(*h)->array[m]=(*h)->array[(*h)->count-1];
		(*h)->count--;
		if(m<(*h)->count)
			PercolateDown(h,m);
	}
}

4) O(log(n))

5) 5 59 42 25 27 8 15 57 36 45 37 20 14 39 18 28 30 34

Back to the list of exercises

Looking for a more challenging exercise, try this one !!

Sorting using the counting sort algorithm

Min-max heaps