In: Computer Science
C++ Heap Tree: Make a program called "priority_queue" that has the following operations using a heap and simulating a prioritized row of integers with higher priority value.
It has to include the following on the code:
push
Description: Add data to prioritized row
Entry: An integer, which you want to add to the prioritized row
Exit: Nothing
Precondition: n is an integer
Postcondition: The prioritized row contains new data.
pop -
Description: Remove the data with the highest priority from the prioritized row
Entry: Nothing
Exit: Nothing
Precondition: That the prioritized row contains at least 1
data.
Postcondition: The prioritized row is left without the data with
the highest priority
top
Description: Returns the value of the data that is with the highest priority in the prioritized row.
Entry: Nothing
Output: The data that has the highest priority within the
prioritized row
Precondition: That the prioritized row contains at least 1
data.
Postcondition: Nothing
empty
Description: Returns a boolean value saying if the prioritized row is empty or has data.
Entry:Nothing
Output: A boolean value that tells whether the prioritized row is
empty or has data.
Precondition: Nothing.
Postcondition: Nothing
size
Description: Returns the amount of data that the prioritized row has
Entry :Nothing
Output :An integer value representing the amount of data in the
prioritized row
Precondition: Nothing.
Postcondition: Nothing
It has to include the next class header(obligatory):
#ifndef MYHEAP_H
#define MYHEAP_H
class MyHeap{
private:
int* values; //where the HEAP values are going to be saved
int size; //Represents how many values the Heap has stored
public:
MyHeap(); //Initialize the attributes. The values attribute initializes it as an empty array size 7
void push(int
n); // Insert a value in the heap. Only when the new value does not
fit in the array
// grow the array to size 2 * n + 1. (Dynamic expansion of the
array)
// That is, if you already have the arrangement with 7 values and
you want to insert another value (The 8th)
// then the array is grown to size 15, the first 7 values of the
original array are copied
// and the 8th value is inserted.
void pop(); //A value is removed from the heap. It is never necessary to decrease the size of the array.
int top(); //Return who is the next element to exit but without deleting it
bool isEmpty(); //returns true if the heap is empty otherwise returns false
int length(); //returns how many elements the heap is storing
};
#endif
SOLUTION: Below here is the code of your problem
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
struct n // node declaration {
int p;
int info;
struct n *l;
};
class Priority_Queue {
private:
//Declare a front pointer f and initialize it to NULL.
n *f;
public:
Priority_Queue() //constructor {
f = NULL;
}
void insert(int i, int p) {
n *t, *q;
t = new n;
t->info = i;
t->p = p;
if (f == NULL || p < f->p) {
t->l= f;
f = t;
} else {
q = f;
while (q->l != NULL && q->l->p <= p)
q = q->l;
t->l = q->l;
q->l = t;
}
}
void del() {
n *t;
if(f == NULL) //if queue is null
cout<<"Queue Underflow\n";
else {
t = f;
cout<<"Deleted item is: "<<t->info<<endl;
f = f->l;
free(t);
}
}
void show() //print queue {
n *ptr;
ptr = f;
if (f == NULL)
cout<<"Queue is empty\n";
else {
cout<<"Queue is :\n";
cout<<"Priority Item\n";
while(ptr != NULL) {
cout<<ptr->p<<" "<<ptr->info<<endl;
ptr = ptr->l;
}
}
}
};
int main() {
int c, i, p;
Priority_Queue pq;
Do//perform switch opeartion {
cout<<"1.Insert\n";
cout<<"2.Delete\n";
cout<<"3.Display\n";
cout<<"4.Exit\n";
cout<<"Enter your choice : ";
cin>>c;
switch(c) {
case 1:
cout<<"Input the item value to be added in the queue : ";
cin>>i;
cout<<"Enter its priority : ";
cin>>p;
pq.insert(i, p);
break;
case 2:
pq.del();
break;
case 3:
pq.show();
break;
case 4:
break;
default:
cout<<"Wrong choice\n";
}
}
while(c != 4);
return 0;
}
**Fell free to ask any queries in the comment section. I am happy to help you. if you like our work, please give Thumbs up**