How to remove an element from a priority queue?

Question

C++ / C#

You need to write a method that will remove the element with the highest priority from the queue. I came up with some kind of check for which element has the highest priority, but I don’t know exactly how to remove it. Maybe there is some type function deleteor some algorithm (except for rewriting all elements except for the one that needs to be deleted)? Here is the code that is available:

template<typename Val, typename Priority>
inline void PriQueue<Val, Priority>::extract() {
    
    size_t biggestindex = 0;
    size_t highestpriority = 0;

    for (size_t i = 0; i < size ; i++)
    {
        if (queue[i].second < highestpriority)
        {
            biggestindex = i;
            highestpriority = queue[i].second;
        }
    }
}

And here is the class code:

template<typename Val, typename  Priority>
class PriQueue
{
private:
    size_t  size = 0;
    size_t capacity;
    size_t step;
    pair<Val, Priority>* queue;

public:
    PriQueue(size_t capacity = 10, size_t  step = 5);
    void add(const pair<Val, Priority>& p);
    void print() const;
    void extract();
};

I will be grateful for any help.

Answer 1

The priority queue is implemented on the basis of a heap or a binary search tree (set). In the first case, the deletion is done like this: Swap the first and last element in the heap. Delete the last one. Then sift the first element down so that it falls into place. In the second case, you just need to remove the begin() element from the set.