Win a copy of Design for the Mind this week in the Design 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
Pie
Posts: 12098
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