+1 vote
58 views
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
edited | 58 views
0
Is it exactly  question given???
0
yes

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
0
i m asking that why they first explicitly used build heap  becz min heap is alredy given.....nd according to them tym complexity is n+nlogn

but it should be only nlogn??? using minheap
0
Use the eg i have given and construct the binary tree then create Heap then you will get it. Step by step follow for each element you will get it

1