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.

  • $\begingroup$ What do you mean by “convert a Max heap to a Min heap in place”? $\endgroup$ Oct 18, 2010 at 10:34
  • 3
    $\begingroup$ 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. $\endgroup$ Oct 18, 2010 at 10:47
  • $\begingroup$ @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). $\endgroup$ Oct 18, 2010 at 11:17
  • $\begingroup$ @Dana: Thanks for the detailed explanation on the problem :). And yes, everything you said is perfectly correct. $\endgroup$ Oct 18, 2010 at 14:07

1 Answer 1


You can just ignore that you have a max heap and build your min heap from it. O(n) time complexity. No need for additional array.

  • 3
    $\begingroup$ Yes, the key thing here is that an arbitrary array can be converted into a heap in $O(n)$ time in place. $\endgroup$ Oct 18, 2010 at 11:51
  • $\begingroup$ Could you please explain how it's O(n) or provide the steps in converting. If I start treating the Max heap as min heap, I think it's O(n)log(n), maybe I am not able to visualize it. $\endgroup$ Oct 18, 2010 at 14:09
  • 2
    $\begingroup$ Search for "Heapify" in Cormen-Leiserson-Rivest book. $\endgroup$
    – slimton
    Oct 18, 2010 at 16:06
  • $\begingroup$ @Gunner, see here: en.wikibooks.org/wiki/Data_Structures/… $\endgroup$
    – rursw1
    Oct 19, 2010 at 9:48
  • 2
    $\begingroup$ @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)$. $\endgroup$
    – slimton
    Oct 19, 2010 at 11:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.