recategorized by
469 views
2 votes
2 votes
Given two inputs bst and min heap tree with $n$ nodes .To get the sorted order which is better and how much time?

In the solution for min heap they first used build heap to create min heap thenm usual $log n$ to take minimum but why they use build heap becz i think input is given as a min heap so have already min heap
recategorized by

1 Answer

0 votes
0 votes
Out of $BST$ and $Min Heap$, it would be better if we select $BST$ bcz

1) In $BST$ we need to perform inorder traversal and we will get the sorted order which will take $O(n)$ time. Whereas if $MinHeap$ is selected then first element will be minimum which can be stored somewhere. Now to maintain the $MinHeap$ property we need to replace minimum element with the last element of the $MinHeap$. Then go for $MinHeapify$ procedure which will take $log(n)$ time. Similarly continue for $n$ times and we will get sorted order in $O(nlog(n))$ time.

 

2) Why Build heap is used? Build heap is used to make the heap either $MinHeap$ or $MaxHeap$ which runs $n$ time and it internally calls $MinHeapify$ or $MaxHeapify$ procedure which takes $logn$ time. Hence $O(nlog(n))$ time is required.

Consider the input array $A$ = $[ 1, 4, 9, 5, 6, 10,11, 2, 3, 7, 8,12,13,14,15]$ now after using build min heap sequence becomes  $A'$ = $[1, 2, 9, 4, 6 ,10, 11,5, 3, 7, 8, 12, 13, 14, 15]$. Now we remove 1 from $MinHeap$ and replace it with last element of $A'$. Sequence becomes $A''$ = $[15, 2, 9, 4, 6 ,10, 11,5, 3, 7, 8, 12, 13, 14]$ and we run $MinHeapify$ on root and get sequence $A''$ = $[2, 4, 9, 3, 6, 10, 11, 5, 15, 7 ,8 , 12, 13, 14 ]$. Now sequence doesn't satisfy $MinHeap$ property. Again $BuildHeap$ runs on $A''$ and we get sequence $A'''$ = $[2, 3, 9, 4, 6, 10, 11, 5, 15, 7, 8, 12, 13, 14]$ which satisfy heap property. Now in the same way we continue and get sorted order.

 

I hope this helps

Related questions

0 votes
0 votes
1 answer
1
Hardik Vagadia asked Sep 6, 2016
535 views
What is the difference between the binary-search-tree property and the min-heap property? Can the min-heap property be used to print out the keys of an n-node tree in sor...
1 votes
1 votes
1 answer
2
A_i_$_h asked Jul 25, 2017
276 views
some random numbers are given and asked to construct a balanced BST..what will be the time complexity?numbers in sorted order are given and asked to construct a balanced ...
1 votes
1 votes
1 answer
3