aspose file tools*
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
Author

Convert max heap to min

mike fusc
Greenhorn

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
Bartender

Joined: Oct 02, 2003
Posts: 11499
    
  16

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: http://aspose.com/file-tools
 
subject: Convert max heap to min