What is the big-O of the function: /** * Standard heapsort. */ template <typenam
ID: 665193 • Letter: W
Question
What is the big-O of the function:
/**
* Standard heapsort.
*/
template <typename Comparable>
void heapsort( vector<Comparable> & a )
{
for(inti=a.size()/2-1;i>=0;--i) /*buildHeap*/
percDown( a, i, a.size( ) );
for(intj=a.size()-1;j>0;--j) {
std::swap( a[ 0 ], a[ j ] );/* deleteMax */
percDown( a, 0, j );
}
}
/**
* Internal method for heapsort.
* i is the index of an item in the heap.
* Returns the index of the left child.
*/
inline int leftChild( int i )
{
return 2 * i + 1;
}
/**
* Internal method for heapsort that is used in deleteMax and buildHeap.
* i is the position from which to percolate down.
* n is the logical size of the binary heap.
*/
template <typename Comparable>
void percDown( vector<Comparable> & a, int i, int n )
{
int child;
Comparable tmp;
for( tmp = std::move(a[i]); leftChild(i) < n; i = child)
{
child = leftChild(i);
if( child != n-1 && a[child]<a[child+1])
++child;
if( tmp < a[child])
a[i] = std::move(a[child]);
else
break;
}
a[ i ] = std::move( tmp );
}
Justify and explain how you arrived at your answer.
Explanation / Answer
Answer:
Suppose an array A with N elements is given. The Heapsort algorithm to sort A consists of the two following phases:
Phase A: Build a Heap H out of the elements of A
Phase B: Repeatedly delete the root element of H
Complexity/ big-O notation:
Phase A: Suppose H is heap. Observe that the number of comparisons to find the appropriate place of a new element ITEM in H cannot exceed the depth of H. Since H is complete tree, its depth is bounded by log2m where m is the number of elements in H.
Accordingly, the total number g(n) of comparisons to insert the n elements of A into H is bounded as follows:
g(n)<=n log2n
Phase B: Suppose H is a complete tree with m elements, and suppose the left and right subtrees of H are heaps and L is the root of H. Observe that reheaping uses 4 comparisions to move the root node L one step down the tree H. Since depth of H does not exceed log2m, reheaping user at most 4 log2 m comparisions to find appropriate place of L in the tree H.
This means that the total number h(n) of comparisions to delete the n element of A from H, which requires reheaping n times, is bounded as follows:
h(n)<=4n log2n
As per the given function code of “heapsort(vector<Comparable> &a)”
-->First traverse to down and rotate the tree to buil heap i.e, “percDown( a, i, a.size( ) )”
--> Second operation of “swap()” delete the maximum
--> Again build the heap by “percDown( a, 0, j )”
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.