Question

please solve this question:

Write a character Max-Heap Builder program in C++. The program should display the menu below. Each item in the menu should be implemented in a function. a. Add a node. One node to be added to the max-heap. b. Delete a node. One node to be deleted from the max-heap. C. Search a node. Returns true if the node exists in the max-heap, otherwise it returns false. d. Print the tree. Prints the heap in level-order traversal. e. Exit: Terminates the program. If the user entered value that is not a letter, the program should display an error message, then display the menu again.

Answer 1

Program

#include <iostream>
#include <vector>

using namespace std;

//class MaxHeap
class MaxHeap
{
private:
vector<char> heap;
int currentSize;
public:
//constructor
MaxHeap()
{
currentSize = 0;
heap.resize(10);
}
/* insert to the heap */
void insertHeap(char x)
{
if (currentSize == heap.size()-1)
heap.resize(heap.size()*2);

currentSize++;
int i = currentSize;

while(x > heap[i/2] && i/2 >= 1){
heap[i] = heap[i/2];
i=i/2;
}
heap[i] = x;
}
/* delete from the heap */
int deleteHeap(char x)
{
int k = searchHeap(x);
if(k==0) return 0;

char t = heap[k];
heap[k] = heap[currentSize];
heap[currentSize] = t;

currentSize--;

x = heap[k];
int parent = k;

while(1)
{
int child = 2*parent;
if(child>=currentSize) break;
if(child+1 <= currentSize &&heap[child+1]>heap[child])
child++;
if(x>=heap[child]) break;
heap[parent] = heap[child];
parent = child;
}
heap[parent] = x;

return 1;
}
/* search into the heap */
int searchHeap(char x)
{
for(int i = 1; i <= currentSize; i++)
if(heap[i]==x)
return i;
return 0;
}

/* Display the MaxHeap */
void display()
{
for(int i = 1; i <= currentSize; i++)
cout<<heap[i]<<" ";
}
};

//function to display menu
void menu()
{
cout<<"1. Add a node"<<endl;
cout<<"2. Delete a node"<<endl;
cout<<"3. Search a node"<<endl;
cout<<"4. Print the tree"<<endl;
cout<<"5. Exit"<<endl;
}

//main function
int main()
{
MaxHeap heap;
int k, op;
char letter;

while(1)
{
menu();
cout<<"Enter option : ";
cin >> op;

switch(op)
{
//insert to the heap
case 1:
cout<<"Enter a letter : ";
cin >> letter;
if(!isalpha(letter))
cout<<"Error: Value is not a letter! "<<endl;
else
heap.insertHeap(letter);
break;
//delete from the heap
case 2:
cout<<"Enter a letter to delete: ";
cin >> letter;
if(!isalpha(letter))
cout<<"Error: Value is not a letter! "<<endl;
else
{
k = heap.deleteHeap(letter);
if(k==0) cout<<"Not found! "<<endl;
}

break;
//search into the heap
case 3:
cout<<"Enter a letter to search: ";
cin >> letter;
if(!isalpha(letter))
cout<<"Error: Value is not a letter! "<<endl;
else
{
k = heap.searchHeap(letter);
if(k==0)
cout<<"Not found! "<<endl;
else
cout<<"Found at "<<k<< " position. "<<endl;
}
break;
//Print the tree
case 4:
heap.display();
break;
//Exit
case 5:
return 0;
}
cout<<endl;
}
return 0;
}

Output:

1. Add a node
2. Delete a node
3. Search a node
4. Print the tree
5. Exit
Enter option : 1
Enter a letter : q

1. Add a node
2. Delete a node
3. Search a node
4. Print the tree
5. Exit
Enter option : 1
Enter a letter : w

1. Add a node
2. Delete a node
3. Search a node
4. Print the tree
5. Exit
Enter option : 1
Enter a letter : e

1. Add a node
2. Delete a node
3. Search a node
4. Print the tree
5. Exit
Enter option : 1
Enter a letter : r

1. Add a node
2. Delete a node
3. Search a node
4. Print the tree
5. Exit
Enter option : 1
Enter a letter : t

1. Add a node
2. Delete a node
3. Search a node
4. Print the tree
5. Exit
Enter option : 1
Enter a letter : y

1. Add a node
2. Delete a node
3. Search a node
4. Print the tree
5. Exit
Enter option : 4
y t w q r e
1. Add a node
2. Delete a node
3. Search a node
4. Print the tree
5. Exit
Enter option : 2
Enter a letter to delete: w

1. Add a node
2. Delete a node
3. Search a node
4. Print the tree
5. Exit
Enter option : 4
y t e q r
1. Add a node
2. Delete a node
3. Search a node
4. Print the tree
5. Exit
Enter option : 2
Enter a letter to delete: y

1. Add a node
2. Delete a node
3. Search a node
4. Print the tree
5. Exit
Enter option : 4
t r e q
1. Add a node
2. Delete a node
3. Search a node
4. Print the tree
5. Exit
Enter option : 3
Enter a letter to search: q
Found at 4 position.

1. Add a node
2. Delete a node
3. Search a node
4. Print the tree
5. Exit
Enter option : 5

N.B. Whether you face any problem or need any modification then share with me in the comment section, I'll happy to help you.