For this computer assignment, you are to write a C++ program to sort numbers usi

Question

For this computer assignment, you are to write a C++ program to sort numbers using the heapsort technique. Your program first builds a heap structure for the numbers. Then, it retrieves these numbers from the heap in a certain order and prints them out on stdout.

The source file assignment7.cc is partially implemented and contains the complete implementation of the main function.

Add and implement the following functions in this source file

-void build_heap ( vector < int >& v, int heap_size, bool (*compar)(int, int) ): This function constructs a heap with heap_size elements in the vector v. Pay attention that elements start at position 1 (position 0 is wasted and ignored) in the vector. compar is a function pointer (predicate) to compare two integers. build_heap will invoke heapify specified below

-void heapify( vector < int >& v, int heap_size, int r, bool (*compar)(int, int) ): This function “heapifies” a tree at the root position r, assuming r’s two sub-trees are already heaps. heap_size specifies the size of the whole heap contained by the vector (the heap starts at position 1 of the vector). This function uses the function pointer compar to compare two elements. This function can be implemented recursively.

-bool less_than ( int e1, int e2 ): This function compares two integers and returns true if e1 is less than e2. Otherwise it returns false. When this function is used as predicate in build_heap, a min heap will be constructed.

-bool greater_than ( int e1, int e2 ): This function compares two integers and returns true if e1 is greater than e2. Otherwise it returns false. When this function is used as predicate in build_heap, a max heap will be constructed.

-void heap_sort ( vector < int >& v, int heap_size, bool (*compar)(int, int) ): This function implement the heap sort algorithm. At beginning the vector v contains a heap. At the end of this function, vector v contains sorted elements. Similar to build_heap, there is a predicate in the parameter list to specify how to compare two elements. If less_than is passed in as argument here, the results are in ascending order. If greater_than is used, the results are in descending order. heap_sort will invoke extract_heap specified below. You can use the STL algorithm reverse if necessary

-int extract_heap ( vector < int >& v, int& heap_size, bool (*compar)(int, int) ): This function extracts the root of the heap recorded in v, fills the root with the last element of the current heap, updates heap_size, “heapifies” at the root, and returns the old root value. This function will invoke heapify specified above.

-void print_vector ( vector < int >& v, int pos, int size ): This function displays size number of elements contained in vector v starting at position pos. It shows 8 elements per line. Each item occupies 5 spaces.

********notes********

-Please implement the algorithms to build the heap and sort by heapsort. Do not invoke the STL algorithms make_heap or heap_sort.

-Please pay extra attention that in this assignment vectors’ elements start at position 1 (instead of position 0) unless otherwise specified.

-Include any necessary headers and add necessary global constants.

-You are not allowed to use any I/O functions from the C library, such as scanf or printf. Instead, use the I/O functions from the C++ library, such as cin or cout

-In the final version of your assignment, you are not supposed to change existing code, including the main method, provided to you in the original source file assginment7.cc.  

- please do not change the name of the file.

***************************assignment7.cc*******************

const int HEAP_SIZE = 50;

int main(int argc, char** argv) {
// ------- creating input vector --------------
vector v;
v.push_back(-1000000); // first element is fake
for (int i=1; i<=HEAP_SIZE; i++)
v.push_back( i );
random_shuffle( v.begin()+1, v.begin()+HEAP_SIZE+1 );

cout << " Current input numbers: " << endl;
print_vector( v, 1, HEAP_SIZE );

// ------- testing min heap ------------------
cout << " Building a min heap..." << endl;
build_heap(v, HEAP_SIZE, less_than);
cout << "Min heap: " << endl;
print_vector( v, 1, HEAP_SIZE );
heap_sort( v, HEAP_SIZE, less_than);

cout << "Heap sort result (in ascending order): " << endl;
print_vector( v, 1, HEAP_SIZE );

// ------- testing max heap ------------------
cout << " Building a max heap..." << endl;
build_heap(v, HEAP_SIZE, greater_than);
cout << "Max heap: " << endl;
print_vector( v, 1, HEAP_SIZE );
heap_sort( v, HEAP_SIZE, greater_than);
cout << "Heap sort result (in descending order): " << endl;

print_vector( v, 1, HEAP_SIZE );

return 0;
}

*****************outout************* (this is the way the out put is suppose to look like )

Current input numbers:
5 29 12 16 25 36 18 37
27 49 34 40 20 3 48 50
26 19 33 41 6 22 8 13
15 43 28 7 46 45 31 39
14 38 4 17 30 44 10 23
9 24 21 35 2 11 32 1
47 42

Building a min heap...
Min heap:
1 2 3 4 6 12 5 14
10 9 8 13 20 7 31 16
26 17 27 23 21 22 11 36
15 43 28 18 46 45 48 39
50 38 37 19 30 44 33 29
41 24 49 35 34 25 32 40
47 42

Heap sort result (in ascending order):
1 2 3 4 5 6 7 8
9 10 11 12 13 14 15 16
17 18 19 20 21 22 23 24
25 26 27 28 29 30 31 32
33 34 35 36 37 38 39 40
41 42 43 44 45 46 47 48
49 50

Building a max heap...
Max heap:

50 47 49 39 46 48 31 35
38 43 45 25 27 29 30 33
34 37 19 41 42 44 23 24
12 26 13 28 14 7 15 32
16 8 17 36 18 9 4 40
20 10 21 2 22 11 5 6
3 1

Heap sort result (in descending order):
50 49 48 47 46 45 44 43
42 41 40 39 38 37 36 35
34 33 32 31 30 29 28 27
26 25 24 23 22 21 20 19
18 17 16 15 14 13 12 11
10 9 8 7 6 5 4 3
2 1

Explanation / Answer

---------Building a Min Heap---------
In this program,take the input according to your need.I will provide you with th easiest code possible.

#include <iostream>
#include <conio.h>
using namespace std;
void min_heapify(int *a,int i,int n)
{
int j, temp;
temp = a[i];
j = 2 * i;
while (j <= n)
{
if (j < n && a[j+1] < a[j])
j = j + 1;
if (temp < a[j])
break;
else if (temp >= a[j])
{
a[j/2] = a[j];
j = 2 * j;
}
}
a[j/2] = temp;
return;
}
void build_minheap(int *a, int n)
{
int i;
for(i = n/2; i >= 1; i--)
{
min_heapify(a,i,n);
}
}
int main()
{
int n, i, x;
cout<<"enter no of elements of array ";
cin>>n;
int a[n];
for (i = 1; i <= n; i++)
{
cout<<"enter element"<<(i)<<endl;
cin>>a[i];
}
build_minheap(a, n);
cout<<"Min Heap ";
for (i = 1; i <= n; i++)
{
cout<<a[i]<<endl;
}
getch();

Output
enter no of elements of array
11
enter element1
2
enter element2
16
enter element3
74
enter element4
58
enter element5
36
enter element6
4
enter element7
28
enter element8
15
enter element9
35
enter element10
82
enter element11
6

Min Heap
2
6
4
15
16
74
28
58
35
82
36

--------------Ascending order heap sorting-----------

// C++ program for implementation of Heap Sort
#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);
}

Output:
Sorted array is
5 6 7 11 12 13

------------------Max Heap---------------------

#include <iostream>
#include <conio.h>
using namespace std;
void max_heapify(int *a, int i, int n)
{
int j, temp;
temp = a[i];
j = 2 * i;
while (j <= n)
{
if (j < n && a[j+1] > a[j])
j = j + 1;
if (temp > a[j])
break;
else if (temp <= a[j])
{
a[j / 2] = a[j];
j = 2 * j;
}
}
a[j/2] = temp;
return;
}
void build_maxheap(int *a,int n)
{
int i;
for(i = n/2; i >= 1; i--)
{
max_heapify(a,i,n);
}
}
int main()
{
int n, i, x;
cout<<"enter no of elements of array ";
cin>>n;
int a[20];
for (i = 1; i <= n; i++)
{
cout<<"enter element"<<(i)<<endl;
cin>>a[i];
}
build_maxheap(a,n);
cout<<"Max Heap ";
for (i = 1; i <= n; i++)
{
cout<<a[i]<<endl;
}
getch();
}

Output
enter no of elements of array
7
enter element1
5
enter element2
9
enter element3
6
enter element4
7
enter element5
1
enter element6
3
enter element7
8
Max Heap
9
7
8
5
1
3
6

---------------Descending order heap sort----------------

#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);
}
Run on IDE

Output:
Sorted array is
13 12 11 7 6 5.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

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