i need implementation to save into heapsort.cpp please // // Laboratory 11, Prog
ID: 3712825 • Letter: I
Question
i need implementation to save into heapsort.cpp please
//
// Laboratory 11, Programming Exercise 2 heapsort.cs
//
// (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;
void moveDown (int arr[], int size, int root )
// 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 largest = root; // Initialize largest as root
int l = 2* root + 1; // left = 2* root + 1
int r = 2* root + 2; // right = 2* root + 2
// If left child is larger than root
if (l < size && arr[l] > arr[largest])
largest = l;
// If right child is larger than largest so far
if (r < size && arr[r] > arr[largest])
largest = r;
// If largest is not root
if (largest != root)
{
swap(arr[i], arr[largest]);
// Recursively heapify the affected sub-tree
moveDown(arr, n, largest);
}
}
//--------------------------------------------------------------------
// main function to do heap sort
void heapSort (int arr[], 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 */
void printArray(int arr[], int size)
{
for (int i=0; i<size; ++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
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.