Page 75, there is this problem :
Quote:
|
You are given a set of integers in an unordered binary tree. Use an array sorting routine to transform the tree into a heap that uses a balanced binary tree as its underlying data structure.
|
Then, it is stated :
Quote:
|
Because you both start and end with binary tree data structures, transforming into an array probably isn’t the most efficient way to accomplish the end goal. You might comment to your interviewer that if not for the requirement to use an array sorting routine, it would be more efficient to simply heapify the nodes of the starting tree: that is, reorder them such that they meet the criteria of a heap. You can heapify the tree in O(n) time, while just the array sort is at least O(n log(n)).
|
This heapify algorithm in O(N) is never explained, and I simply don't see how it works...
Binary tree to heap in O(N)
