PQ.cpp

#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct Node{
    string task;
    int priority;

    Node(string t, int p){
        task = t;
        priority = p;
    }
};

void upHeapify(vector<Node*>& heap,int index){
    int parentIndex = (index - 1)/2;
    Node* temp;

    while(parentIndex >= 0 && heap[parentIndex]->priority < heap[index]->priority){
        temp = heap[parentIndex];
        heap[parentIndex] = heap[index];
        heap[index] = temp;
        index = parentIndex;
        parentIndex = (index - 1)/2;
    }
}
void downHeapify(vector<Node*>& heap){
    int LChild;
    int RChild;
    int i = 0;
    int size = heap.size();
    int largest;
    Node* temp;
    while (true)
    {
        LChild = 2 * i + 1;
        RChild = 2 * i + 2;
        largest = i;

        if (LChild < size && heap[LChild] > heap[largest])
        {
            largest = LChild;
        }
        if (RChild < size && heap[RChild] > heap[largest])
        {
            largest = RChild;
        }
        if (largest == i)
        {
            break;
        }
        temp = heap[i];
        heap[i] = heap[largest];
        heap[largest] = temp;

        i = largest;
    }
    
}
void Delete(vector<Node*>& heap){
    Node* temp = heap[heap.size() - 1];
    heap[heap.size() - 1] = heap[0];
    heap[0] = temp;
    delete heap[heap.size()-1];
    heap.pop_back();
    downHeapify(heap);
}
void displayHeap(vector<Node*>heap){
    for (size_t i = 0; i < heap.size(); i++)
    {
        cout<<heap[i]->task<<": "<<heap[i]->priority<<endl;
    }
    
}
int main(int argc, char const *argv[])
{
    int priority;
    string task;
    vector<Node*> heap;

    for (size_t i = 0; i < 10; i++)
    {
        cout<<"Enter the name of the task: ";
        cin>>task;
        cout<<"Enter the task's priority: ";
        cin>>priority;
        Node* node = new Node(task,priority);
        heap.push_back(node);
        if (i != 0)
        {
            upHeapify(heap,i);
        }
        cout<<endl;
    }
    Delete(heap);
    displayHeap(heap);
    return 0;
}