What is the big-O of the function: template <typename Comparable> void heapsort(
ID: 3858502 • Letter: W
Question
What is the big-O of the function:
template <typename Comparable>
void heapsort(vector<Comparable &a)
Justify and explain how you arrived at the answer
* Standard heapsort. 3 4 template 5 void heapsort( vectorcComparable> & a) for( int i a.size()/2-1; i 0; - /* buildHeap/ percDown (a, i, a.size)) for( int j = a.size( ) -l; j > 0; --j ) 10 std::swap( al 0], al j]) percDown ( a, 0, j); /* deleteMax / 12 13 14 15 16 17 18 * Internal method for heapsort. * i is the index of an item in the heap. * Returns the index of the left child. 20 21 inline int 1eftChild int i) 23 24 return 2 *i+1; 26 27 28 29 * 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. 31 template 32 void percDown( vector Comparable> & a, int i, int n) int child; Comparable tmp; 35 37 38 39 40 for( tmp = std ::move( a[ i ] ); 1eftChild( i ) n; i-child ) child = leftChild( i ); if( child != n- 1 && a[ child ] a[ child + 1 ] ) ++child; al i 1 break; std: :move( tmp); 42 43 if( tmpExplanation / Answer
Code Of Heap Sort in C++ FYI
#include <iostream>
using namespace std;
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i)
{
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// main function to do heap sort
void heapSort(int arr[], int n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
swap(arr[0], arr[i]);
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
/* A utility function to print array of size n */
void printArray(int arr[], int n)
{
for (int i=0; i<n; ++i)
cout << arr[i] << " ";
cout << " ";
}
// Driver program
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);
heapSort(arr, n);
cout << "Sorted array is ";
printArray(arr, n);
}
#include <iostream>
using namespace std;
// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
int largest = i; // Initialize largest as root
int l = 2*i + 1; // left = 2*i + 1
int r = 2*i + 2; // right = 2*i + 2
// If left child is larger than root
if (l < n && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < n && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != i)
{
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
// main function to do heap sort
void heapSort(int arr[], int n)
{
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i=n-1; i>=0; i--)
{
// Move current root to end
swap(arr[0], arr[i]);
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
/* A utility function to print array of size n */
void printArray(int arr[], int n)
{
for (int i=0; i<n; ++i)
cout << arr[i] << " ";
cout << " ";
}
// Driver program
int main()
{
int arr[] = {12, 11, 13, 5, 6, 7};
int n = sizeof(arr)/sizeof(arr[0]);
heapSort(arr, n);
cout << "Sorted array is ";
printArray(arr, n);
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.