The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+1 vote
60 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
asked in Algorithms by Loyal (6.7k points)
edited by | 60 views
0
Is it exactly  question given???
0
yes

1 Answer

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
answered by Active (1.4k points)
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

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
48,756 questions
52,850 answers
183,548 comments
68,743 users