File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
The moose likes Beginning Java and the fly likes Convert max heap to min Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Convert max heap to min" Watch "Convert max heap to min" New topic

Convert max heap to min

mike fusc

Joined: Mar 07, 2010
Posts: 15
Im reviewing for a final and I came across a review problem that says to convert a max string heap stored in an array to a min heap.

Now i know the answer to the question because it's not asking to code, but how would one code this in O(n) time. Basically I am thinking since the children are (2k+1) and (2k+2) in the heap you can use that to your advantage, but I'm lost other then calling SiftUp to traverse up the tree at each node.
fred rosenberger
lowercase baba

Joined: Oct 02, 2003
Posts: 11913

can't you ignore the fact that you have a heap (of any kind), traverse through the elements one at a time, and insert them into a new min-heap?

I don't recall if building a heap from scratch is O(n) or not, so I may be way wrong...

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
I agree. Here's the link:
subject: Convert max heap to min
It's not a secret anymore!