<p>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.</p>

CC BY-SA 2.5
2010-10-18T11:51:10.950Z
Yes, the key thing here is that an arbitrary array can be converted into a heap in $O(n)$ time in place.
Jukka Suomela
CC BY-SA 2.5
2010-10-18T14:09:25.053Z
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.
Shamim Hafiz - MSFT
CC BY-SA 2.5
2010-10-18T16:06:38.737Z
Search for "Heapify" in Cormen-Leiserson-Rivest book.
slimton
CC BY-SA 2.5
2010-10-19T09:48:07.220Z
@Gunner, see here: http://en.wikibooks.org/wiki/Data_Structures/Min_and_Max_Heaps#Inserting_a_value_into_the_heap
rursw1
CC BY-SA 2.5
2010-10-19T10:45:13.407Z
@slimton: Doesn't the heapify operation take O(nlogn)?
Shamim Hafiz - MSFT
CC BY-SA 2.5
2010-10-19T11:34:10.600Z
@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)$.
slimton
CC BY-SA 2.5
2010-10-19T11:47:06.430Z
Ok I understand now.
Shamim Hafiz - MSFT
CC BY-SA 2.5
2010-10-18T10:56:28.657Z
2010-10-18T15:16:59.280Z
2010-10-18T15:16:59.280Z
rursw1
<p>I was just wondering if this was possible?</p>

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

CC BY-SA 2.5
2010-10-18T10:34:37.153Z
What do you mean by “convert a Max heap to a Min heap in place”?
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-18T10:47:53.437Z
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.
Dana Moshkovitz
CC BY-SA 2.5
2010-10-18T11:17:48.777Z
@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).
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-18T14:07:02.250Z
@Dana: Thanks for the detailed explanation on the problem :). And yes, everything you said is perfectly correct.
Shamim Hafiz - MSFT
<ds.algorithms><ds.data-structures>
Is it possible to convert a Max heap to a Min heap in place?
Shamim Hafiz - MSFT
# Is it possible to convert a Max heap to a Min heap in place?

(Asked by: username_0 on 2010-10-18)

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.

**Tags:** ds.algorithms, ds.data-structures

> **Comments:**
> **username_1**: What do you mean by “convert a Max heap to a Min heap in place”?  
> **username_2**: 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.  
> **username_1**: @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).  
> **username_0**: @Dana: Thanks for the detailed explanation on the problem :). And yes, everything you said is perfectly correct.  

---

## 1 answers

### Answer by username_3 on 2010-10-18. Score: 23 | Accepted answer

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.

> **Comments:**
> **username_4**: Yes, the key thing here is that an arbitrary array can be converted into a heap in $O(n)$ time in place.  
> **username_0**: 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.  
> **username_5**: Search for "Heapify" in Cormen-Leiserson-Rivest book.  
> **username_3**: @Gunner, see here: http://en.wikibooks.org/wiki/Data_Structures/Min_and_Max_Heaps#Inserting_a_value_into_the_heap  
> **username_0**: @username_5: Doesn't the heapify operation take O(nlogn)?  
> **username_5**: @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)$.  
> **username_0**: Ok I understand now.  

---

