//client.cpp #include <iostream> #include \"maxHeap.h\" using namespace std; int

Question

//client.cpp

#include <iostream>
#include "maxHeap.h"

using namespace std;

int main()
{
MaxHeap h(11);
h.insert(3);
h.insert(2);
h.insert(15);
h.insert(5);
h.insert(4);
h.insert(45);
h.removeAt(2);
cout << h.extractMax() << " ";
cout << h.getMax() << endl;
  
int a[7] = {2, 3, 4, 5, 6, 7, 1};
MaxHeap h2(7);
h2.heapify(a, 7);
cout << h2.extractMax() << " ";
cout << h2.getMax() << " " << endl;
return 0;
}

//maxHeap.h

#ifndef HEAP_H
#define HEAP_H
class MaxHeap
{
int *arr;       // pointer to array of elements in heap
int capacity;   // maximum possible size of min heap
int size;       // Current number of elements in min heap
  
int parent(int i);
int left(int i);
int right(int i);
bool isLeaf(int i);
void siftup(int i);
void siftdown(int i);
public:
class Overflow{};
class Underflow{};
MaxHeap(int capacity);
int getSize();
int getMax();
void insert(int k);
int extractMax();
int removeAt(int i);
void heapify(int *array, int len);
};
#endif

PLEASE COMPLETE MAXHEAP.CPP IN ACCORDANCE TO MAXHEAP.H AND CLIENT.CPP. NEED SERIOUS HELP HERE...PLEASE.

//maxHeap.cpp

#include "maxHeap.h"

/*MaxHeap::MaxHeap(int cap)
{
;;
}*/

Explanation / Answer

#include "maxHeap.h"

//constructor
MaxHeap::MaxHeap(int capacity)
{
arr = new int[capacity]; // create an array with size capacity
this->capacity = capacity;
this->size = 0; //initalise size to zero
  
}

//get the number of elements in array
int MaxHeap::getSize()
{
return size;
}

//get parent index
int MaxHeap::parent(int child)
{
if(child % 2 == 0)
return (child /2) -1;
else
return (child/2);
}

//get index of left child
int MaxHeap::left(int parent)
{
return (2 * parent +1);
}

//get index of right node
int MaxHeap::right(int parent)
{
return (2 * parent +2);
}

//heapify downwards in case of replacement or deletion
void MaxHeap::siftup(int i)
{
if(i == 0)
return; //only one element in the array
  
int parent_index = parent(i); // get the index of the parent
  
if(arr[parent_index] < arr[i])   
{
int temp = arr[parent_index]; //if value at parent index is less than inserted value
arr[parent_index] = arr[i]; // swap the values
arr[i] = temp;
siftup(parent_index); // loop untill it satisfies parent child max heap relationship
}
}

//insert element into heap
void MaxHeap::insert(int k)
{
arr[size] = k; // insert the value into array
siftup(size);
size++; //increment the size of the array
for(int i = 0;i<size;i++)
{
cout<<arr[i]<<" ";
}
cout<<endl;
}

//get max element in the heap
int MaxHeap::getMax()
{
return arr[0]; // maximum value will be at index 0
}

//check if index is a leaf
bool MaxHeap::isLeaf(int i)
{
if(i>=size)
return true;
return false;
}

//heapify downwards in case of deletion or replacement
void MaxHeap::siftdown(int i)
{
int l = left(i);
int r = right(i);
  
if(isLeaf(l))
return;
  
int maxIndex = i;
if(arr[l] > arr[i])
{
maxIndex = l;
}
  
if(!isLeaf(r) && (arr[r] > arr[maxIndex]))
{
maxIndex = r;
}
  
if(maxIndex != i)
{
int temp = arr[i];
arr[i] = arr[maxIndex];
arr[maxIndex] = temp;
siftdown(maxIndex);
}
}

//extract the maximum and heapify
int MaxHeap::extractMax()
{

int max = arr[0];
arr[0] = arr[size - 1];

size--;
  
siftdown(0);
return max;
}

//heapify the array
void MaxHeap::heapify(int *array, int len)
{
size = len;
arr = array;
  
for(int i=size-1; i>=0; --i)
{
siftdown(i);
}
}

//remove an element at arbitary index

int MaxHeap::removeAt(int k)
{
int r = arr[k];
  
arr[k] = arr[size -1]; // replace with rightmost leaf
size-- ;
int p = parent(k);
if(k == 0 || arr[k] < arr[p])
siftdown(k);
else
siftup(k);
return r;   
}

Related Questions

Navigate

• Browse (All)
• Browse #
• Subjects

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