On Mar 13, 12:02 am, "Karthik Singaram L" <[EMAIL PROTECTED]>
wrote:
> Given a binary tree in an array in the standard representation with left and
> right nodes being stored in 2i and 2i+1 for a node at position i. Assuming
> that the array indices start at 1.
This is how a "heap" is organized. I think you are looking for
"heapsort". Look at any standard book on data structures/algorithms
viz Data structures by tanenbaum. This is an O(nlogn) algorithm
> How do you perform a sort of the array with constant space and O(n) time.
Not possible with what you've asked for above! Heapsort/Binary-tree
sort works in O(nlogn) time. However there are sorts like counting
sort, radix sort that work in O(n) time because they are NOT
comparison sorts! you can find them in the same book as above. You may
look at "Introduction to algorithms: Cormen" or a book by Horowitz/
sahni.
Regards,
Nupul
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
