Question

Write a complete C++ program to implements a Min-heap.

Each node will contain a single integer data element. Initialize the Min-heap to contain 5 nodes, with the values 8, 12, 24, 32, 42.

The program should allow for the insertion and deletion of nodes while maintaining a Min-Heap.

The program should allow the user to output data in Preorder, Inorder and Postorder.

The program should loop with menu items for each of the above objectives and the choice to quit

Here's the code:

**EDIT: Need help in outputting data into Preorder, Inorder and Postorder, plus ensuring the nodes are implemented correctly (I think I overlooked this part). **

#include studio.h
#include isotream

int array[100]; // variable for array to store up to 100 elements
int n;

using namespace std;
void display();
void delete_elem(int num);

void heapify(int index,int n){
if(index >= n)return;
  

int left = 2*index;
int right = 2*index + 1;
int mx_ind = index;
if(left < n and array[left] > array[mx_ind]){
mx_ind = left;
}
if(right < n and array[right] > array[mx_ind]){
mx_ind = right;
}
if(mx_ind != index){
swap(array[mx_ind],array[index]);
heapify(mx_ind,n);
}

}
int insert(int num, int location)
{
int parentnode;
while (location > 0)
{
parentnode =(location - 1)/2;
if (num <= array[parentnode])
{
array[location] = num;
return location;
}
array[location] = array[parentnode];
location = parentnode;
}
array[0] = num;
return 0;
}

int main()
{
int choice, num;
n = 0;
while(1)
{
printf("1.Insert the element \n");
printf("2.Delete the element \n");
printf("3.Display all elements \n");
printf("4.Quit \n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter the element to be inserted to the list : ");
scanf("%d", &num);
insert(num, n);
n = n + 1;
break;
case 2:
printf("Enter the elements to be deleted from the list: ");
scanf("%d", &num);
delete_elem(num);
break;
case 3:
display();
break;
case 4:
exit(0);
default:
printf("Invalid choice \n");
}
}
}

void display()
{
int i;
if (n == 0)
{
printf("Heap is empty \n");
return;
}
for (i = 0; i < n; i++)
printf("%d ", array[i]);
printf("\n");
}

void delete_elem(int num)
{
int left, right, i, temp, parentnode;

for (i = 0; i < num; i++) {
if (num == array[i])
break;
}
if (num != array[i])
{
printf("%d not found in heap list\n", num);
return;
}
array[i] = array[n - 1];
n = n - 1;
parentnode =(i - 1) / 2;
if (array[i] > array[parentnode])
{
insert(array[i], i);
return;
}
left = 2 * i + 1;
right = 2 * i + 2;
while (right < n)
{
if (array[i] >= array[left] && array[i] >= array[right])
return;
if (array[right] <= array[left])
{
temp = array[i];
array[i] = array[left];
array[left] = temp;
i = left;
}
else
{
temp = array[i];
array[i] = array[right];
array[right] = temp;
i = right;
}
left = 2 * i + 1;
right = 2 * i + 2;
}
if (left == n - 1 && array[i])
{
temp = array[i];
array[i] = array[left];
array[left] = temp;
}
}

Answer 1

The above doesn't implement heapify function correctly and chances have been made to that function, go through the source code below to see the changes made. Implementation of a preorder,inorder, postorder has been made in below source code. Compare the above source code with the below source code to see the changes made to make the program work correctly. Moreover the above function created max-heap but we require min-heap and below implementation has made the required changes for that.

#include<bits/stdc++.h>
#include<stdio.h>
int arr[100]; // variable for array to store up to 100 elements
int n;

using namespace std;
void display();
void delete_elem(int num);
//Definition for preorder,postorder,inorder
void inorder(int idx){
if(idx>=n)return ;
int left=2*idx+1;
int right=2*idx+2;
inorder(left);
cout<<arr[idx]<<" ";
inorder(right);
}
void preorder(int idx){
if(idx>=n)return;
int left=2*idx+1;
int right=2*idx+2;
cout<<arr[idx]<<" ";
preorder(left);
preorder(right);
}
void postorder(int idx){
if(idx>=n)return;
int left=2*idx+1;
int right=2*idx+2;
postorder(left);
postorder(right);
cout<<arr[idx]<<" ";
}

void heapify(int index,int n){
if(index >= n)return;

int left = 2*index+1;// add 1 to get left child index
int right = 2*index + 2;// add two to get right child index
int mx_ind = index;
if(left < n and arr[left] < arr[mx_ind]){//use arr[left]<arr[mx_ind],we are creating min heap
mx_ind = left;
}
if(right < n and arr[right] < arr[mx_ind]){
mx_ind = right;
}
if(mx_ind != index){
swap(arr[mx_ind],arr[index]);
heapify(mx_ind,n);
}

}
int insert(int num, int location)
{
int parentnode;
while (location > 0)
{
parentnode =(location - 1)/2;
if (num <= arr[parentnode])
{
arr[location] = arr[parentnode];
}
else break;
location = parentnode;
}
arr[location] = num;
return 0;
}

int main()
{
int choice, num;
n = 0;
// To insert 5 elements in the heap make use of heapify function
arr[0]=8,arr[1]=12,arr[2]=24,arr[3]=32,arr[4]=42;
n=5;
for(int i=n/2-1;i>=0;i--){// Initializing our heap with these 5 values
heapify(n,i);
}
while(1)
{
printf("1.Insert the element \n");
printf("2.Delete the element \n");
printf("3.Display all elements \n");
printf("4.Quit \n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch(choice)
{
case 1:
printf("Enter the element to be inserted to the list : ");
scanf("%d", &num);
insert(num, n);
n = n + 1;
break;
case 2:
printf("Enter the elements to be deleted from the list: ");
scanf("%d", &num);
delete_elem(num);
break;
case 3:
display();
cout<<"Inorder display ";
inorder(0);cout<<endl;
cout<<"Preorder display ";
preorder(0);cout<<endl;
cout<<"Postorder display ";
postorder(0);cout<<endl;
break;
case 4:
exit(0);
default:
printf("Invalid choice \n");
}
}
}

void display()
{
int i;
if (n == 0)
{
printf("Heap is empty \n");
return;
}
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}

void delete_elem(int num)
{
int left, right, i, temp, parentnode;

for (i = 0; i < num; i++) {
if (num == arr[i])
break;
}
if (num != arr[i])
{
printf("%d not found in heap list\n", num);
return;
}
arr[i] = arr[n - 1];
n = n - 1;
// simply use heapify at index i and the subtree will follow heap property after running function
heapify(i,n);

}