Can priority queue be made by using simple queues

Is priority queue just a sorted queue? Can it be made by creating a simple queue and sorting it afterwards? https://www.quora.com/What-is-the-difference-between-a-priority-queue-and-a-queue?share=1 I found this link and it states that they priority queue can be made by Re-arrange the Queue at insertion time, and put the recently inserted object at the appropriate priority place. I wanted to be certain about it because some of my peers stated that its not possible, but if we make a queue which adheres to priority, wouldn't it make the queue a priority queue?

Solution

A priority queue is an abstract data-structure with a few required operations:

check emptiness (is_empty);
insert element by "priority" (insert);
find and remove the element with the highest priority (pop).

There are many way to implement this, but you are usually looking for a O(log n) (amortized) complexity for both pop and insert.

A queue is an abstract data-structure where you insert at the back and remove at the front, so it cannot be used to implement a priority queue (there is no "ordering", except first-in first-out).

The simplest way to implement a priority queue is usually to use a binary heap. A minimalist C++ implementation using a std::vector<int> as a backend and the heap operations defined in the standard library could be:

#include <algorithm>
#include <vector>

using priority_queue = std::vector<int>;

bool is_empty(priority_queue const& q) { return q.empty(); }

void insert(priority_queue &q, int value) { 
    q.push_back(value);
    std::push_heap(std::begin(q), std::end(q));
}

int pop(priority_queue &q) {
    std::pop_heap(std::begin(q), std::end(q));
    const int value = q.back();
    q.pop_back();
    return value;
}

This gives you (amortized) O(log n) complexity for both insert and pop.