Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Convert max heap to min

 
mike fusc
Greenhorn
Posts: 15
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 12126
30
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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...
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic