C++ Implementation of the moveDown function. There is a spot below to input the

Question

 C++ Implementation of the moveDown function. There is a spot below to input the code, thank you! -------------------------------------------------------------------------------------------------  //  (Shell) heapSort() function   template < typename DataType > void moveDown ( DataType dataItems [], int root, int size )  // Restores the binary tree that is rooted at root to a heap by moving // dataItems[root] downward until the tree satisfies the heap property. // Parameter size is the number of data items in the array.  {     // Your code here  }  //--------------------------------------------------------------------  template < typename DataType > void heapSort ( DataType dataItems [], int size )  // Heap sort routine. Sorts the data items in the array in ascending // order based on priority.  {     DataType temp;   // Temporary storage     int j;     // Loop counter      // Build successively larger heaps within the array until the     // entire array is a heap.      for ( j = (size-1)/2 ; j >= 0 ; j-- )         moveDown(dataItems,j,size);      // Swap the root data item from each successively smaller heap with     // the last unsorted data item in the array. Restore the heap after     // each exchange.      for ( j = size-1 ; j > 0 ; j-- )     {         temp = dataItems[j];         dataItems[j] = dataItems[0];         dataItems[0] = temp;         moveDown(dataItems,0,j);     } } 

Explanation / Answer

#include <iostream>

using namespace std;

template < typename DataType >
void moveDown ( DataType dataItems [], int root, int size )
{
int largest = root; // Initialize largest as root
int l = 2*root + 1; // left = 2*i + 1
int r = 2*root + 2; // right = 2*i + 2

// If left child is larger than root
if (l < size && dataItems[l] > dataItems[largest])
largest = l;

// If right child is larger than largest so far
if (r < size && dataItems[r] > dataItems[largest])
largest = r;

// If largest is not root
if (largest != root)
{
DataType temp = dataItems[root];
dataItems[root] = dataItems[largest];
dataItems[largest] = temp;

// Recursively heapify the affected sub-tree
moveDown(dataItems, largest, size);
}
}
//--------------------------------------------------------------------

template < typename DataType >
void heapSort ( DataType dataItems [], int size )

// Heap sort routine. Sorts the data items in the array in ascending
// order based on priority.

{
DataType temp; // Temporary storage
int j; // Loop counter

// Build successively larger heaps within the array until the
// entire array is a heap.

for ( j = (size-1)/2 ; j >= 0 ; j-- )
moveDown(dataItems,j,size);

// Swap the root data item from each successively smaller heap with
// the last unsorted data item in the array. Restore the heap after
// each exchange.

for ( j = size-1 ; j > 0 ; j-- )
{
temp = dataItems[j];
dataItems[j] = dataItems[0];
dataItems[0] = temp;
moveDown(dataItems,0,j);
}
}

/* A utility function to print array of size n */
template < typename DataType >
void printArray(DataType dataItems[], int n)
{
for (int i=0; i<n; ++i)
cout << dataItems[i] << " ";
cout << " ";
}

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);

return 0;
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.