No heapify will not barf. Here is how it goes:
Whenever you get a node value > root value (you have already determined the
root value in first scan) you are sure that this isnt the actual value can't
be in a heap. So determine actual value.
if (pres_node_value > root_value say R) //Value keeps frequency and isnt
actual
Call get_actual_value (pres_node_value)
get_actual_value (pres_node_value)
{
frequency_of_occurence = pres_node_value /R => Quotient
actual_value = pres_node_value % R => remainder
So e.g. when 2 is repeated twice and root value is 3 you will store (2
+ 3 +3 = 8). When you see 8 you know it is > ROOT = 3 so get_actual_value
(8) will give 8/3 = 2 => frequency and 8% 3 = 2 => actual value.
}
Rest of heapify insertion works as usual. This way nothing in heap changes,
no property. And by the way how can you save bits in an integer ?? It is
always 4 bytes (on most of platforms) whether its = 1 or 1 + 1000 ? If you
said that there could be overflow I would still have agreed but I dont think
you are saving bits. In fact in your solution a whole new 4 byte chunk is
used when you keep something like 2:1 which is O(K) space and violates the
in-place property which says that extra space should have upper bound logn.
Thanks,
Sachin
On Thu, May 20, 2010 at 7:59 PM, Piyush Verma <[email protected]> wrote:
>
> @shachin,when u add value of root in the child of root then for insertion
> of new element when heap is called(so heapify is called) so now this child
> becomes root which is not desired..............
> plzzzzzzzzzz correct me if i m wrong
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected]<algogeeks%[email protected]>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
