Implementing a minheap Write a program that user to perform

Implementing a min-heap Write a program that user to perform the following operations on a min-heap H using an array. create-min-heap(): create a min-heap; delete-min(): delete the minimum key from the min-heap; change-key(k, k\'): replace the key k with k\'; insert (k): insert key k to the min-heap; print(): print out the properties of the heap H, including the size of the heap and the current minimum key; print-content(): print out the content of the heap by iterating all the keys in the underlying array sequentially; Note: In order to relieve the effort for grading the programming problem, you must have your program developed with Dev C++. This light-weight IDE is enough for you to develop your code for this problem and it is easy to use. From now on, we will not accept the code developed with other IDE\'s. Besides, all the files should be named in English. If your code can not be executed under Dev C++ or have the filenames in Chinese, your code will not count and this programming part will be 0. Execution Example [s35980040@sun ~]$ min-heap The min-heap is empty with size = 0 create-min-heap 42 51 32 64 87 21 18 The min-heap is of size 7 and the current minimum is 18. print content 18 51 21 64 87 42 32 insert 15 The min-heap is of size 8 and the current minimum is 15. print content 15 18 21 51 87 42 32 64 delete-min The min-heap is of size 7 and the current minimum is 18. change-key 18 70 The min-heap is of size 7 and the current minimum is 21.

Solution

MinHeap.h

#include \"vector\"
using namespace std;

class MinHeap
{
private:
vector<int> HeapArray;
void BubbleDown(int index);
void BubbleUp(int index);
void creat_minheap();
int heapsize;

public:
MinHeap(int* array, int length);
MinHeap(const vector<int>& vector);
MinHeap();

void Insert(int newValue);
int GetMin();
void DeleteMin();

void change_key(int k,int knew);
void print();
void print_content();
};

=====================================================================

MinHeap.cpp

#include \"MinHeap.h\"

MinHeap::MinHeap(int* array, int length) : HeapArray(length)
{
for(int i = 0; i < length; ++i)
{
HeapArray[i] = array[i];
}
heapsize=length;

creat_minheap();
}

MinHeap::MinHeap(const vector<int>& vector) : HeapArray(vector)
{
creat_minheap();
}

MinHeap::MinHeap()
{
}

void MinHeap::creat_minheap()
{
//int length = HeapArray.size();
for(int i=heapsize-1; i>=0; --i)
{
BubbleDown(i);
}
}

void MinHeap::change_key(int k,int knew)
{
int pos = std::find(HeapArray.begin(), HeapArray.end(), k) - HeapArray.begin();

HeapArray[pos] =knew;
creat_minheap();
}

void MinHeap::BubbleDown(int index)
{
//int length = HeapArray.size();
int leftChildIndex = 2*index + 1;
int rightChildIndex = 2*index + 2;

if(leftChildIndex >= heapsize)
return; //index is a leaf

int minIndex = index;

if(HeapArray[index] > HeapArray[leftChildIndex])
{
minIndex = leftChildIndex;
}
  
if((rightChildIndex < heapsize) && (HeapArray[minIndex] > HeapArray[rightChildIndex]))
{
minIndex = rightChildIndex;
}

if(minIndex != index)
{
  
int temp = HeapArray[index];
HeapArray[index] = HeapArray[minIndex];
HeapArray[minIndex] = temp;
BubbleDown(minIndex);
}
}

void MinHeap::BubbleUp(int index)
{
if(index == 0)
return;

int parentIndex = (index-1)/2;

if(HeapArray[parentIndex] > HeapArray[index])
{
int temp = HeapArray[parentIndex];
HeapArray[parentIndex] = HeapArray[index];
HeapArray[index] = temp;
BubbleUp(parentIndex);
}
}

void MinHeap::Insert(int newValue)
{
heapsize = HeapArray.size();
HeapArray[heapsize] = newValue;

BubbleUp(heapsize);
heapsize++;
}

void MinHeap::print()
{
cout<<\"Current minimum is \"<<GetMin()<<\"\ \";
cout<<\"Size of heap is \"<<HeapArray.size()<<\"\ \";
}

void MinHeap::print_content()
{int i;
for( i=0; i<heapsize; ++i)
{
cout <<HeapArray[i] << \" \";

}

}
int MinHeap::GetMin()
{
return HeapArray[0];
}
  
void MinHeap::DeleteMin()
{
heapsize = HeapArray.size();

if(heapsize == 0)
{
return;
}
  
HeapArray[0] = HeapArray[heapsize-1];
HeapArray.pop_back();
heapsize--;

BubbleDown(0);
}

==============================================================

main.cpp

#include<bits/stdc++.h>
#include \"MinHeap.cpp\"
using namespace std;

int main()
{
int array[] = {10, 4, 5, 30, 3, 300};

MinHeap *ptr;
  

  

int flag=1;
MinHeap minHeap(array, 6);
  
while(flag)
{
cout<<\"1)Create min heap\ 2)Delete minimum\ 3)Change key\ 4)Insert\ 5)Print\ 6)Print content\ 7)Exit\ \";

int ch;
cin>>ch;

switch(ch)
{
case 1:

  
ptr=&minHeap;
break;

case 2:
cout<<ptr->GetMin() <<\" is deleted\ \";
ptr->DeleteMin();
break;

case 3:
int k,k1;
cout<<\"Enter old key\ \";
cin>>k;
cout<<\"Enter new key\ \";
cin>>k1;
ptr->change_key(k,k1);
break;

case 4:cout<<\"Enter value to insert\ \";
int v;
cin>>v;
ptr->Insert(v);
cout<<\"Inserted\ \";
break;
case 5:
ptr->print();
break;
case 6:ptr->print_content();
break;
case 7:flag=0;
break;

}
}

return 0;
}

==========================================================================

==============================================================================

akshay@akshay-Inspiron-3537:~/Chegg$ g++ main2.cpp
akshay@akshay-Inspiron-3537:~/Chegg$ ./a.out
1)Create min heap
2)Delete minimum
3)Change key
4)Insert
5)Print
6)Print content
7)Exit
1
1)Create min heap
2)Delete minimum
3)Change key
4)Insert
5)Print
6)Print content
7)Exit
6
3 4 5 30 10 300 1)Create min heap
2)Delete minimum
3)Change key
4)Insert
5)Print
6)Print content
7)Exit
2
3 is deleted
1)Create min heap
2)Delete minimum
3)Change key
4)Insert
5)Print
6)Print content
7)Exit
6
4 10 5 30 300 1)Create min heap
2)Delete minimum
3)Change key
4)Insert
5)Print
6)Print content
7)Exit
5
Current minimum is 4
Size of heap is 5
1)Create min heap
2)Delete minimum
3)Change key
4)Insert
5)Print
6)Print content
7)Exit
3
Enter old key
4
Enter new key
3
1)Create min heap
2)Delete minimum
3)Change key
4)Insert
5)Print
6)Print content
7)Exit
6
3 10 5 30 300 1)Create min heap
2)Delete minimum
3)Change key
4)Insert
5)Print
6)Print content
7)Exit
4
Enter value to insert
400
Inserted
1)Create min heap
2)Delete minimum
3)Change key
4)Insert
5)Print
6)Print content
7)Exit
6
3 10 5 30 300 400 1)Create min heap
2)Delete minimum
3)Change key
4)Insert
5)Print
6)Print content
7)Exit
7