Please Implament heapsort. there is a spot where you would input the code.this i
ID: 3821554 • Letter: P
Question
Please Implament heapsort. there is a spot where you would input the code.this is C++ programming (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
Function implemented and made as bold where ever I changed for quick reference.. please check
#include <algorithm> // include this statement
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.
{
int max_value = root; //iniitializing root value as max heap max number
int left = 2*root + 1; // declaring left child
int right = 2*root + 2; // declaring right child
// check left child value is more than root
if (left < size && dataItems[left] > dataItems[max_value])
max_value = left;
// check right child value is more than root
if (right < size && dataItems[right] > dataItems[max_value])
max_value = right;
// if root is not maximum, then do this
if (max_value != root)
{
std::swap(dataItems[root], dataItems[max_value]);
// call the method recursively until heap property success
moveDown(dataItems, max_value, 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);
}
}