InstructionsPlease read the following instructions carefully before solving & submitting assignment: It should be clear that your assignment will not get any credit (marks) if: Ø The assignment is submitted after due date.Ø The submitted assignment file is not in .cpp format.Ø The submitted assignment file does not open or corrupted.Ø The assignment is copied (from other student or ditto copy from handouts or internet).Uploading instructionsØ Do not wait for grace day. Grace Day is given only if there is problem with LMS on due date. Submit your solution within due date. Ø Note that no assignment will be accepted through email if there is any problem in LMS on grace day.ObjectiveThe objective of this assignment is o To make you familiar with working and implementation of heap data structure. For any query about the assignment, contact at cs301@vu.edu.pk | |

Marks: 20 | |

Question: Marks 20Write to C++ program min heap. Your program should fulfill requirements given below in points a) and b). implementData: 18, 31, 82, 85, 37, 20, 23, 79, 47, 51, 96, 97, 42, 94, 57, 29a) Consider the data given above and build min heap of odd nodes/values only using insert method you learned in handouts/video lectures. b) Consider the data given above and build min heap of all nodes/values in data using buildHeap method given in handouts/video lectures. Assignment solution instructions:· Graphical representation of odd min heap using insert() method and min using buildHeap() method is given below for your understanding. · Given data should be used for input to heap in the form of array. · For Odd min heap construction use data given above while constructing min heap, check if the number/node is odd then use it for heap construction. In case of even discard it and move to next number. Data after extracting odd nodes/values : 31, 85, 37, 23, 79, 47, 51, 97, 57, 29 b):Data: 18, 31, 82, 85, 37, 20, 23, 79, 47, 51, 96, 97, 42, 94, 57, 29 Sample Output:For any query send email at CS301@vu.edu.pk | |

Lectures Covered: This assignment covers Lecture # 23 - 33Deadline: Your assignment must be uploaded / submitted on / before, July 26, 2018. |

Solution:

/** https://virtualuniversitystudies.blogspot.com/**/

#include <iostream>

#include <conio.h>

using namespace std;

class Heap {

public:

Heap(int capacity = 100);

void insert(const int &n);

void buildHeap(int* anArray, int n);

void perculateDown(int hole);

void printHeap(int size);

private:

int* array ;

int capacity;

int currentSize;

};

Heap::Heap(int capacity) {

array = new int[capacity + 1];

currentSize=0;

}

void Heap::insert(const int & x) {

int hole = ++currentSize;

for(; hole > 1 && x < array[hole/2]; hole /= 2)

array[hole] = array[hole / 2];

array[hole] = x;

}

void Heap::buildHeap(int* Array, int n) {

for(int i = 1; i <= n; i++)

array[i] = Array[i-1];

currentSize = n;

for(int i = currentSize / 2; i > 0; i--)

perculateDown(i);

}

void Heap::perculateDown(int hole) {

int tmp = array[hole];

int child;

for(; hole * 2 <= currentSize; hole = child) {

child = hole * 2;

if(child != currentSize && array[child+1] < array[child])

child++;

if(array[child] < tmp)

array[hole] = array[child];

else

break;

}

array[hole] = tmp;

return;

}

void Heap::printHeap(int size) {

for(int i=1; i<=size; i++) {

cout << array[i] << " ";

}

}

int main() {

int Array[] = {18, 31, 82, 85, 37, 20, 23, 79, 47, 51, 96, 97, 42, 94, 57, 29};

Heap minHeap;

for(int i=0; i<17; i++) {

if(!(Array[i] % 2 == 0))

minHeap.insert(Array[i]);

}

cout << "Odd Min Heap using insert method: " << endl;

minHeap.printHeap(10);

minHeap.buildHeap(Array,16);

cout << "\nMin Heap using build method: " << endl;

minHeap.printHeap(16);

getch();

}