In this programming project, you will be implementing the data structure min-hea

Question

In this programming project, you will be implementing the data structure min-heap. You should use the C++ programming language, not any other programming language. Also, your program should be based on the g++ compiler on general.asu.edu. All programs will be compiled and graded on general.asu.edu, a Linux based machine. If you program does not work on that machine, you will receive no credit for this assignment. You will need to submit it electronically a the blackboard, in one zip file, named name-F name, where Lname is your last name and Fname is your first name. The zip file should contain a set of files that are absolutely necessary to compile and execute your program. If you program does not compile on general.asu.edu, you will receive 0 n this project You need to define the following data types. ELEMENT is a data type that contains a field named key, which is of type int. In later assignments, you will have to add on other fields to ELEMENT, without having to change the functions. Note that ELEMENT should not be of type int HEAP is a data type that contains three fields named capacity (of type int), size (of type int) and H (an array of type ELEMENT with index ranging from 0 to capacity) The functions that you are required to implement are Initialize(n) which returns an object of type HEAP with capacity n and size 0. BuildHeap(heap, A), where heap is a HEAP object and A is an array of type ELEMENT. This function copies the elements in A into heap->H and uses the linear time build heap algorithm to obtain a heap of size size(A) Insert(heap, k) which inserts an element with key equal to k into the min-heap heap DeleteMin(heap) which deletes the element with minimum key and returns it to the caller DecreaseKey(heap, element, value) which decreases the key field of element to value, if the latter is not larger than the former. Note that you have make necessary adjustment to make sure that heap order is maintained. printHeap(heap) which prints out the heap information, including capacity, size, and the key fields of the elements in the array with index going from 1 to size.

Explanation / Answer

CODE:

// A C++ program to demonstrate common Binary Heap Operations
#include<iostream>
#include<string>
#include<climits>
#include <fstream>

using namespace std;

// Prototype of a utility function to swap two integers
void swap(int *x, int *y);

// A class for Min Heap
class MinHeap
{
int *harr; // pointer to array of elements in heap
int capacity; // maximum possible size of min heap
int heap_size; // Current number of elements in min heap
public:
// Constructor
MinHeap();

// to heapify a subtree with root at given index
void MinHeapify(int );

int parent(int i) { return (i-1)/2; }

// to get index of left child of node at index i
int left(int i) { return (2*i + 1); }

// to get index of right child of node at index i
int right(int i) { return (2*i + 2); }

// to extract the root which is the minimum element
int extractMin();

// Decreases key value of key at index i to new_val
void decreaseKey(int i, int new_val);

// Returns the minimum key (key at root) from min heap
int getMin() { return harr[0]; }

// Deletes a key stored at index i
void deleteKey(int i);

// Inserts a new key 'k'
void insertKey(int k);

// read frmm File and populate the heap
void readFromFile();

// set the size of the HEAP.
void setHeapSize(int n);

//print the heap elements.
void printHeap();
};

// Constructor: Builds a heap from a given array a[] of given size
MinHeap::MinHeap(){ }

// Inserts a new key 'k'
void MinHeap::insertKey(int k)
{
if (heap_size == capacity)
{
cout << " Overflow: Could not insertKey ";
return;
}

// First insert the new key at the end
heap_size++;
int i = heap_size - 1;
harr[i] = k;

// Fix the min heap property if it is violated
while (i != 0 && harr[parent(i)] > harr[i])
{
swap(&harr[i], &harr[parent(i)]);
i = parent(i);
}
}

// Decreases value of key at index 'i' to new_val. It is assumed that
// new_val is smaller than harr[i].
void MinHeap::decreaseKey(int i, int new_val)
{
harr[i] = new_val;
while (i != 0 && harr[parent(i)] > harr[i])
{
swap(&harr[i], &harr[parent(i)]);
i = parent(i);
}
}

// Method to remove minimum element (or root) from min heap
int MinHeap::extractMin()
{
if (heap_size <= 0)
return INT_MAX;
if (heap_size == 1)
{
heap_size--;
return harr[0];
}

// Store the minimum value, and remove it from heap
int root = harr[0];
harr[0] = harr[heap_size-1];
heap_size--;
MinHeapify(0);

return root;
}

// This function deletes key at index i. It first reduced value to minus
// infinite, then calls extractMin()
void MinHeap::deleteKey(int i)
{
decreaseKey(i, INT_MIN);
extractMin();
}

// A recursive method to heapify a subtree with root at given index
// This method assumes that the subtrees are already heapified
void MinHeap::MinHeapify(int i)
{
int l = left(i);
int r = right(i);
int smallest = i;
if (l < heap_size && harr[l] < harr[i])
smallest = l;
if (r < heap_size && harr[r] < harr[smallest])
smallest = r;
if (smallest != i)
{
swap(&harr[i], &harr[smallest]);
MinHeapify(smallest);
}
}

void MinHeap::readFromFile(){
ifstream myfile ("HEAPinput.txt");
string line;
getline (myfile,line);
setHeapSize(stoi(line));
if (myfile.is_open())
{
while ( getline (myfile,line) )
{
insertKey(stoi(line));
}
myfile.close();
}
}

void MinHeap::setHeapSize(int n){
heap_size = 0;
capacity = n;
harr = new int[n];
}
// A utility function to swap two elements
void swap(int *x, int *y)
{
int temp = *x;
*x = *y;
*y = temp;
}

void MinHeap::printHeap() {
for(int i=0;i<heap_size;i++){
cout << harr[i] << endl;
}
}
// Driver program to test above functions
int main()
{
string input;
while(1){
cout << "Enter the menu: " << endl;
cout << "Exit: press S" << endl;
cout << "Create: press C and the capacity of heap as n" << endl;
cout << "Read from input file. Press R" << endl;
cout << "Print: Press W" << endl;
cout << "Insert: Press I k" << endl;
cout << "Delete: Press D" << endl;
cout << "Decrease key value: press K i v" << endl;

getline(cin,input);

MinHeap h;
switch(input[0]){

case 'C': h.setHeapSize(input[2] - '0');
break;
case 'R': {h.readFromFile();}
break;
case 'W': h.printHeap();
break;
case 'I': h.insertKey(input[2] - '0');
break;
case 'D': h.deleteKey(0);
break;
case 'K': h.decreaseKey(input[2]-'0', input[4]='0');
break;

case 'S': exit(1);
break;

default: cout << "Enter correctly!!!!" << endl;
}
}

return 0;
}

Please have the below file in the same location as the cpp file

HEAPinput.txt

5
3
2
1
15
8

OUTPUT:

$ g++ minheap.cpp
$ ./a.out
Enter the menu:
Exit: press S
Create: press C and the capacity of heap as n
Read from input file. Press R
Print: Press W
Insert: Press I k
Delete: Press D
Decrease key value: press K i v
R
Enter the menu:
Exit: press S
Create: press C and the capacity of heap as n
Read from input file. Press R
Print: Press W
Insert: Press I k
Delete: Press D
Decrease key value: press K i v
W
1
3
2
15
8
Enter the menu:
Exit: press S
Create: press C and the capacity of heap as n
Read from input file. Press R
Print: Press W
Insert: Press I k
Delete: Press D
Decrease key value: press K i v
D
Enter the menu:
Exit: press S
Create: press C and the capacity of heap as n
Read from input file. Press R
Print: Press W
Insert: Press I k
Delete: Press D
Decrease key value: press K i v
W
2
3
8
15
Enter the menu:
Exit: press S
Create: press C and the capacity of heap as n
Read from input file. Press R
Print: Press W
Insert: Press I k
Delete: Press D
Decrease key value: press K i v
I 4
Enter the menu:
Exit: press S
Create: press C and the capacity of heap as n
Read from input file. Press R
Print: Press W
Insert: Press I k
Delete: Press D
Decrease key value: press K i v
W
2
3
8
15
4
Enter the menu:
Exit: press S
Create: press C and the capacity of heap as n
Read from input file. Press R
Print: Press W
Insert: Press I k
Delete: Press D
Decrease key value: press K i v
D 2 1
Enter the menu:
Exit: press S
Create: press C and the capacity of heap as n
Read from input file. Press R
Print: Press W
Insert: Press I k
Delete: Press D
Decrease key value: press K i v
W
3
4
8
15
Enter the menu:
Exit: press S
Create: press C and the capacity of heap as n
Read from input file. Press R
Print: Press W
Insert: Press I k
Delete: Press D
Decrease key value: press K i v
S

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

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