Almost complete binary trees can be represented compactly using arrays, where the children of $a[i]$ are $a[2i]$ and $a[2i+1]$, with the root being $a[1]$ (assume index of the array starts at 1 for this problem).
Given an almost complete binary search represented in such a manner: i.e. given the array $A$ representing the tree, can you give an $O(n)$ time and $O(1)$ space algorithm (WORD RAM model) which will sort the array?
For example if the tree is [image swiped from someone's webpage in cmu]
the corresponding array would be
$$ [10, 6, 18, 4, 8, 15, 21] $$
and your algorithm needs to sort it so that it becomes
$$ [4, 6, 8, 10, 15, 18, 21] $$
[I have labelled this hard, because the solution I have uses a result which is hard. Hint: You can find that result on this blog]
[Solution]
Given an almost complete binary search represented in such a manner: i.e. given the array $A$ representing the tree, can you give an $O(n)$ time and $O(1)$ space algorithm (WORD RAM model) which will sort the array?
For example if the tree is [image swiped from someone's webpage in cmu]
the corresponding array would be
$$ [10, 6, 18, 4, 8, 15, 21] $$
and your algorithm needs to sort it so that it becomes
$$ [4, 6, 8, 10, 15, 18, 21] $$
[Solution]
No comments:
Post a Comment