# Is it possible to convert a Max heap to a Min heap in place?

I was just wondering if this was possible?

Surely there maybe some naive methods of doing so, but I was just wondering if someone can suggest efficient ways to do so.

• What do you mean by “convert a Max heap to a Min heap in place”? Oct 18, 2010 at 10:34
• Let's see if I remember... :) A "heap" is a data structure that holds numbers (usually, plus some data associated with them). It's always a complete binary tree (as much as possible), so it can be stored in an array. A "max heap" is a tree where the children are always at most their father. A "min heap" is a tree where the children are always at least their father. "In place" means not copying the data as an intermediate step, without using more space than the space of the existing heap. Oct 18, 2010 at 10:47
• @Dana: Thank you for a reply. I thought that the question might be about using the code for a Max heap to implement a Min heap (which was trivial). Oct 18, 2010 at 11:17
• @Dana: Thanks for the detailed explanation on the problem :). And yes, everything you said is perfectly correct. Oct 18, 2010 at 14:07

• Yes, the key thing here is that an arbitrary array can be converted into a heap in $O(n)$ time in place. Oct 18, 2010 at 11:51
• @Gunner. Perhaps I should have said "look for Build-heap" in CRS. It takes O(n) time. The point is that each element takes time proportional to its height to find its place in the heap, so the total running time is $\sum_{h = 1}^{\log_2 n} \Theta(h) n/2^h$, which is $O(n)$. Oct 19, 2010 at 11:34