I need to implement a heapsort in C++ using vector implementation, please fill i
ID: 3709923 • Letter: I
Question
I need to implement a heapsort in C++ using vector implementation, please fill in the heapsort function and buildHeap function (last 2 functions in the code). If one of the other functions look incorrect feel free to change those as well.
CODE:
#include "maxheap.hpp"
#include
#include
#include
MaxHeap::MaxHeap() {}
MaxHeap::~MaxHeap() {}
/*
ALL YOUR CODE GOES HERE
The methods below either
- don't do anything at all, or
- return 0 just so that the code compiles
You have to implement every method in this class
*/
int MaxHeap::size() {
return arr.size();
return 0;
}
int MaxHeap::left(int parent) {
return (2*parent + 1);
return 0;
}
int MaxHeap::right(int parent) {
return (2*parent + 2);
return 0;
}
int MaxHeap::parent(int child) {
return (child - 1 )/ 2;
return 0;
}
void MaxHeap::insert(int element) {
arr.push_back(element); // add new element to the end of vector
int index = size() - 1;
percolateUp(index);
}
int MaxHeap::deleteMax() {
arr[0] = arr.back();
arr.pop_back();
percolateDown(0);
return 0;
}
void MaxHeap::display() {
vector::iterator it;
cout << "MaxHeap:- ";
for(it=arr.begin(); it!=arr.end(); ++it) {
cout << *it << " ";
}
cout << endl;
}
void MaxHeap::percolateUp(int index) {
if (index && arr[parent(index)] < arr[index])
{
swap(arr[index], arr[parent(index)]);
percolateUp(parent(index));
}
}
void MaxHeap::percolateDown(int index) {
int left_ind = left(index);
int right_ind = right(index);
int largest = index;
if (left_ind < size() && arr[left_ind] > arr[index])
{
largest = left_ind;
}
if (right_ind < size() && arr[right_ind] > arr[largest])
{
largest = right_ind;
}
if (largest != index)
{
swap(arr[index], arr[largest]);
percolateDown(largest);
}
}
void MaxHeap::heapify(int i) {
int left_ind = left(i);
int right_ind = right(i);
int smallest = i;
if (left_ind < size() && arr[left_ind] < arr[i])
smallest = left_ind;
if (right_ind < size() && arr[right_ind] < arr[smallest])
smallest = right_ind;
if (smallest != i)
{
swap(arr[i], arr[smallest]);
heapify(smallest);
}
}
void MaxHeap::buildHeap(vector A,int n) {
}
void MaxHeap::heapsort(vector& A,int n) {
}
Explanation / Answer
void MaxHeap::buildHeap(vector A,int n) {
int largest = i;
int l = left(i);
int r = right(i);
// If left child is larger than root
if (l < n && A[l] > A[largest])
largest = l;
if (r < n && A[r] > A[largest])
largest = r;
if (largest != i)
{
int temp = A[i];
A[i] = A[largest];
A[largest] = temp;
buildHeap(A, n, largest);
}
}
void MaxHeap::heapsort(vector& A,int n) {
for (int i = n / 2 - 1; i >= 0; i--)
buildHeap(A, n, i);
for (int i=n-1; i>=0; i--)
{
int temp = A[0];
A[0] = A[i];
A[i] = temp;
buildHeap(A, i, 0);
}
}