Question

Language C++

Implement a Priority Queue with a Binary HEAP. Use a Max Heap.

Create a class called Node: Have a Name and Priority.Data set - 10 is the highest priority, 1 is lowest priority.

Enqueue and dequeue in the following order.

Function  Name, Priority

Enqueue  Joe, 3

Enqueue  Fred,1

Enqueue Tuyet,9

Enqueue  Jose, 6

Dequeue

Enqueue  Jing, 2

Enqueue  Xi, 5

Enqueue  Moe, 3

DequeueEnqueue  Miko, 7

Enqueue Vlady, 8

Enqueue Frank, 9

Enqueue  Anny, 3

DequeueEnqueue  Xi, 2

Enqueue  Wali, 2

Enqueue  xChe, 6

Enqueue  xVerra, 8

Dequeue

Dequeue

Dequeue

Dequeue

Dequeue

Dequeue

Dequeue

Dequeue

Dequeue

Dequeue

Dequeue

Answer 1

Answer:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
struct node
{
   int priority;
   int content;
   struct node *connect;
};

class Priority_Queue
{
    private:
        node *top;
    public:
        Priority_Queue()
        {
            top = NULL;
        }
        void insert(int value, int priority)
        {
            node *read, *q;
            read = new node;
            read->content = value;
            read->priority = priority;
            if (top == NULL || priority < top->priority)
            {
                read->connect = top;
                top = read;
            }
            else
            {
                q = top;
                while (q->connect != NULL && q->connect->priority <= priority)
                    q=q->connect;
                read->connect = q->connect;
                q->connect = read;
            }
        }
        void del()
        {
            node *read;
            if(top == NULL)
                cout<<"Queue Underflow\n";
            else
            {
                read = top;
                cout<<"Deleted value is: "<<read->content<<endl;
                top = top->connect;
                free(read);
            }
        }
      
        void display()
        {
            node *input;
            input = top;
            if (top == NULL)
                cout<<"Queue is empty\n";
            else
            {   cout<<"Queue is :\n";
                cout<<"Priority       value\n";
                while(input != NULL)
                {
                    cout<<input->priority<<"                 "<<input->content<<endl;
                    input = input->connect;
                }
            }
        }
};

int main()
{
    int option, value, priority;
    Priority_Queue pq;
    do
    {
        cout<<"1.Insert\n";
        cout<<"2.Delete\n";
        cout<<"3.Display\n";
        cout<<"4.Quit\n";
        cout<<"Enter your option : ";
        cin>>option;
        switch(option)
        {
        case 1:
            cout<<"Input the value value to be added in the queue : ";
            cin>>value;
            cout<<"Enter its priority : ";
            cin>>priority;
            pq.insert(value, priority);
            break;
        case 2:
            pq.del();
            break;
        case 3:
            pq.display();
            break;
        case 4:
            break;
        default :
            cout<<"Wrong option\n";
        }
    }
    while(option != 4);
    return 0;
}