Question

(C++. Please don't use #include <bits/stdc++.h>) This lab exercises your understanding of using a Heap to create a Priority Queue

Follow these steps:

• Declare an integer array to use for the heap (size of 20 to 30 elements)
• Create an insertion function (and any needed helper functions) that creates a min-heap (smallest priority is most important)
• Create a remove function (and any needed helper functions) that removes the min value from the heap and returns it
• In main, call the insertion function with at least 15 random values
• In main, call the remove function for all values and print them to the screen (format the numbers so they all fit in a single screen – perhaps 5 to 10 values on each line?)
• Repeat the insertion and remove/print for a second set of random values before ending the program

Answer 1

#include <iostream>

using namespace std;

int arr[100], 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");
} /*End of display()*/

void insert(int num, int loc)
{
int par;
while (loc > 0)
{
par = (loc - 1) / 2;
if (num <= arr[par])
{
arr[loc] = num;
return;
}
arr[loc] = arr[par];
loc = par;
} /*End of while*/
arr[0] = num; /*assign num to the root node */
} /*End of insert()*/

void del(int num)
{
int left, right, i, temp, par;

for (i = 0; i < n; i++)
{
if (num == arr[i])
break;
}
if (num != arr[i])
{
printf("%d not found in heap\n", num);
return;
}
arr[i] = arr[n - 1];
n = n - 1;
par = (i - 1) / 2; /*find parent of node i */
if (arr[i] > arr[par])
{
insert(arr[i], i);
return;
}
left = 2 * i + 1; /*left child of i*/
right = 2 * i + 2; /* right child of i*/
while (right < n)
{
if (arr[i] >= arr[left] && arr[i] >= arr[right])
return;
if (arr[right] <= arr[left])
{
temp = arr[i];
arr[i] = arr[left];
arr[left] = temp;
i = left;
}
else
{
temp = arr[i];
arr[i] = arr[right];
arr[right] = temp;
i = right;
}
left = 2 * i + 1;
right = 2 * i + 2;
} /*End of while*/
if (left == n - 1 && arr[i] < arr[left]) /* right==n */
{
temp = arr[i];
arr[i] = arr[left];
arr[left] = temp;
}
} /*End of del()*/

int main()
{

insert(10, n);
n = n + 1;
cout << "insert:";
display();
cout << endl;
insert(20, n);
n = n + 1;
cout << "insert:";
display();
cout << endl;
insert(40, n);
n = n + 1;
cout << "insert:";
display();
cout << endl;
insert(33, n);
n = n + 1;
cout << "insert:";
display();
cout << endl;
insert(26, n);
n = n + 1;
cout << "insert:";
display();
cout << endl;
insert(56, n);
n = n + 1;
cout << "insert:";
display();
cout << endl;
insert(90, n);
n = n + 1;
cout << "insert:";
display();
cout << endl;
insert(34, n);
n = n + 1;
cout << "insert:";
display();
cout << endl;
insert(25, n);
n = n + 1;
cout << "insert:";
display();
cout << endl;
insert(78, n);
n = n + 1;
cout << "insert:";
display();
cout << endl;

del(10);
cout << "Delete 10:";
display();
cout << endl;
del(20);
cout << "Delete 20:";
display();
cout << endl;
del(40);
cout << "Delete 40:";
display();
cout << endl;
del(33);
cout << "Delete 33:";
display();
cout << endl;
del(26);
cout << "Delete 26:";
display();
cout << endl;
del(56);
cout << "Delete 56:";
display();
cout << endl;
del(90);
cout << "Delete 90:";
display();
cout << endl;
del(34);
cout << "Delete 34:";
display();
cout << endl;
del(25);
cout << "Delete 25:";
display();
cout << endl;
del(78);
cout << "Delete 78:";
display();
cout << endl;
}

***********************************************************************************************************************************

In case of any doubt do ask in the comment section