Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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?

like image 517
user1940350 Avatar asked Dec 31 '12 23:12

user1940350


1 Answers

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

  1. Building the heap in O(n) time,
  2. Converting the heap to a BST in O(n) time, and
  3. 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!

like image 87
templatetypedef Avatar answered Jan 01 '23 20:01

templatetypedef