Question

Design and implement the Heap.h header using the given Heap class below:

template
class Heap
public:
Heap();
Heap(const T elements[], int arraySize); //
Remove the root from the heap and maintain the heap property
T remove() throw (runtime_error);
// Insert element into the heap and maintain the heap property
void add(const T& element);
// Get the number of element in the heap
int getSize() const;
private:
vector v;
Removing the root in a heap - after the root is removed, the tree must be rebuilt to maintain the heap property:
Move the last node to replace the root;
Let the root be the current node;
While (the current node has children and the current node is smaller than one of its children) Swap the current node with the larger of its children; The current node now is one level down;}
Adding a new node - to add a new node to the heap, first add it to the end of the heap and then rebuild the tree as follows:
Let the last node be the current node;
While (the current node is greater than its parent)
{Swap the current node with its parent; The current node now is one level up:}
To test the header file, write the heapSort function and use the following main program:
#include
#include "Heap.h"
using namespace std;
template
void heapSort(T list[], int arraySize) 1/
your code here .. p
int main()
const int SIZE = 9;
int list[] = { 1, 2, 3, 4, 9, 11, 3, 1, 2 }; heapSort(list, SIZE);
cout << "Sorted elements using heap: \\";
for (int i = 0; i < SIZE; i++) cout << list[i] << " ";
cout << endl;
system("pause");
return;
Sample output:
Sorted elements using heap:
1 1 2 3 3 4 7 9 11

Answer 1

See explaination

Step-by-step explanation:

/* Heap.h */

#ifndef HEAP_H

#define HEAP_H

#include<iostream>

using namespace std;

template<class T>

class Heap

{

public:

//constructor

Heap()

{

arr = nullptr;

size = maxsize = 0;

}

//parameterized constructor

Heap(const T elements[], int arraySize)

{

maxsize = arraySize;

size = 0;

arr = new T[maxsize];

for(int i=0; i<maxsize; i++)

{

add(elements[i]);

}

}

//Remove the root from the heap and maintain the heap property

T remove() //code is altered

{

T item = arr[0];

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

size--;

T x = arr[0];

int parent = 0;

while(1)

{

int child = 2*parent + 1;

if(child>=size) break;

if(child+1 < size &&arr[child+1]>arr[child])

child++;

if(x>=arr[child]) break;

arr[parent] = arr[child];

parent = child;

}

arr[parent] = x;

return item;

}

//Insert element into the heap and maintain the heap property

void add(const T&element)

{

if(size==0)

{

arr[size] = element;

size++;

return;

}

T x = element;

int child = size;

int parent = (child-1)/2;

while(child>0 && x>arr[parent])

{

arr[child] = arr[parent];

child = parent;

parent = (child-1)/2;

}

arr[child] = x;

size++;

}

//Get the number of element in the heap

int getSize() const

{

return size;

}

private:

T *arr; //code is altered

int size, maxsize;

};

#endif // HEAP_H

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

/* main.cpp */

#include<iostream>

#include "Heap.h"

using namespace std;

template <typename T>

void heapSort(T list[], int arraySize)

{

Heap<T> heap(list, arraySize);

int n = heap.getSize();

for(int i=n-1; i>0; i--)

{

list[i] = heap.remove();

}

}

int main()

{

const int SIZE = 9;

int list[] = {1, 7, 3, 4, 9, 11, 3, 1, 2};

heapSort<int>(list, SIZE);

cout << "Sorted elements using heap: \\";

for (int i = 0; i < SIZE; i++)

cout << list[i] << " ";

cout <<endl;

system("pause");

return 0;

}