Find the median of the values and move the lower values to left and higher
values to the right. This can be done in o(n). now do the same on both the
parts recursively. And the total complexity will be o(nlogk).
On Fri, May 21, 2010 at 1:12 PM, Shachin Sharma <shac...@gmail.com> wrote:
> 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 <114piy...@gmail.com> 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 algoge...@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
>> .
>> 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 algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
<<Bharath>>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
