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$
$\endgroup$
-
$\begingroup$ What do you mean by “convert a Max heap to a Min heap in place”? $\endgroup$ – Tsuyoshi Ito Oct 18 '10 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$ – Dana Moshkovitz Oct 18 '10 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$ – Tsuyoshi Ito Oct 18 '10 at 11:17
-
$\begingroup$ @Dana: Thanks for the detailed explanation on the problem :). And yes, everything you said is perfectly correct. $\endgroup$ – Shamim Oct 18 '10 at 14:07
$\begingroup$
$\endgroup$
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$ – Jukka Suomela Oct 18 '10 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$ – Shamim Oct 18 '10 at 14:09
-
2$\begingroup$ Search for "Heapify" in Cormen-Leiserson-Rivest book. $\endgroup$ – slimton Oct 18 '10 at 16:06
-
$\begingroup$ @Gunner, see here: en.wikibooks.org/wiki/Data_Structures/… $\endgroup$ – rursw1 Oct 19 '10 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 '10 at 11:34
