Converting a heap to a BST in O(n) time?
I think that I know the answer and the minimum complexity is O(nlogn). But is there any way that I can make an binary search tree from a heap in O(n) complexity?
There is no algorithm for building a BST from a heap in O(n) time. The reason for this is that given n elements, you can build a heap from them in O(n) time. If you have a BST for a set of values, you can sort them in O(n) time by doing an inorder traversal. If you could build a BST from a heap in O(n) time, you could then have an O(n) sorting algorithm by
- Building the heap in O(n) time,
- Converting the heap to a BST in O(n) time, and
- Walking the BST in O(n) time to get a sorted sequence.
Therefore, it is not possible to convert a heap to a BST in O(n) time (or in o(n log n) time, where o is little-o notation).
However, it is possible to build a BST from a heap in O(n log n) time by repeatedly dequeueing the maximum value from the BST and inserting it as the rightmost node in the tree. (You’d need to store a pointer there for fast access; just inserting at the root repeatly would take O(n2) time.)
Hope this helps!
- Database Administration Tutorials
- Programming Tutorials & IT News
- Linux & DevOps World
- Entertainment & General News
- Games & eSport