Implementing min function

Question

Good day, I found this priority queue implementation and I am trying to get a min version of it (instead of max). I have no idea where to start. I tried mixing the signs of the functions (naive attempt) but it didn't get me far. Any help of how to implement it and a few words explaining it are very wellcome. The source is below: Note I have left it's comments

#include <iostream>
#include <vector>
#include <assert.h>
using namespace std;
class PriorityQueue
{
    vector<int> pq_keys;
    void shiftRight(int low, int high);
    void shiftLeft(int low, int high);
    void buildHeap();
public:
    PriorityQueue(){}
    PriorityQueue(vector<int>& items)
    {
        pq_keys = items;
        buildHeap();
    }
    /*Insert a new item into the priority queue*/
    void enqueue(int item);
    /*Get the maximum element from the priority queue*/
    int dequeue();
    /*Just for testing*/
    void print();
};
void PriorityQueue::enqueue(int item)
{
    pq_keys.push_back(item);
    shiftLeft(0, pq_keys.size() - 1);
    return;
}
int PriorityQueue::dequeue()
{
    assert(pq_keys.size() != 0);
    int last = pq_keys.size() - 1;
    int tmp = pq_keys[0];
    pq_keys[0] = pq_keys[last];
    pq_keys[last] = tmp;
    pq_keys.pop_back();
    shiftRight(0, last-1);
    return tmp;
}
void PriorityQueue::print()
{
    int size = pq_keys.size();
    for (int i = 0; i < size; ++i)
        cout << pq_keys[i] << "   ";
    cout << endl;
}
void PriorityQueue::shiftLeft(int low, int high)
{
    int childIdx = high;
    while (childIdx > low)
    {
        int parentIdx = (childIdx-1)/2;
        /*if child is bigger than parent we need to swap*/
        if (pq_keys[childIdx] > pq_keys[parentIdx])
        {
            int tmp = pq_keys[childIdx];
            pq_keys[childIdx] = pq_keys[parentIdx];
            pq_keys[parentIdx] = tmp;
            /*Make parent index the child and shift towards left*/
            childIdx = parentIdx;
        }
        else
        {
            break;
        }
    }
    return;
}
void PriorityQueue::shiftRight(int low, int high)
{
    int root = low;
    while ((root*2)+1 <= high)
    {
        int leftChild = (root * 2) + 1;
        int rightChild = leftChild + 1;
        int swapIdx = root;
        /*Check if root is less than left child*/
        if (pq_keys[swapIdx] < pq_keys[leftChild])
        {
            swapIdx = leftChild;
        }
        /*If right child exists check if it is less than current root*/
        if ((rightChild <= high) && (pq_keys[swapIdx] < pq_keys[rightChild]))
        {
            swapIdx = rightChild;
        }
        /*Make the biggest element of root, left and right child the root*/
        if (swapIdx != root)
        {
            int tmp = pq_keys[root];
            pq_keys[root] = pq_keys[swapIdx];
            pq_keys[swapIdx] = tmp;
            /*Keep shifting right and ensure that swapIdx satisfies
            heap property aka left and right child of it is smaller than
            itself*/
            root = swapIdx;
        }
        else
        {
            break;
        }
    }
    return;
}
void PriorityQueue::buildHeap()
{
    /*Start with middle element. Middle element is chosen in
    such a way that the last element of array is either its
    left child or right child*/
    int size = pq_keys.size();
    int midIdx = (size -2)/2;
    while (midIdx >= 0)
    {
        shiftRight(midIdx, size-1);
        --midIdx;
    }
    return;
}
int main()
{
//example usage
    PriorityQueue asd;
    asd.enqueue(2);
    asd.enqueue(3);
    asd.enqueue(4);
    asd.enqueue(7);
    asd.enqueue(5);
    asd.print();
    cout<< asd.dequeue() << endl;
    asd.print();
    return 0;
}

Answer 1

Easier:

std::prioroty_queue<int, std::vector<int>, std::greater<int>> my_queue;

If this is part of an exercise, then I suggest following the standard library's design principles: split the problem up:

1. data storage (e.g. std::vector)
2. sorting or "heapifying" algorithm (c.f. std::make_heap etc.)
3. ordering criteria (to be used by 2. above)

Your class should give you some leeway to change any of these independently. With that in place, you can trivially change the "less-than" ordering for a "greater than" one.

Answer 2

Well generally in such problems, i.e. algorithms based on comparison of elements, you can redefine what does (a < b) mean. (That is how things in standard library work by the way. You can define your own comparator.)

So if you change it's meaning to the opposite. You will reverse the ordering.

You need to identify every comparison of elements, and switch it. So for every piece of code like this

  /*if child is bigger than parent we need to swap*/
    if (pq_keys[childIdx] > pq_keys[parentIdx])

invert it's meaning/logic.

Simple negation should do the trick:

  /*if child is NOT bigger than parent we need to swap*/
    if !(pq_keys[childIdx] > pq_keys[parentIdx])

You do not even need to understand algorithm. Just inverse meaning of what lesser element is.

Edit: Additional note. You could actually refactor it into some kind of bool compare(T a, T b). And use this function where comparison is used. So whenever you want to change the behaviour you just need to change one place and it will be consistent. But that is mostly to avoid work to look for every such occurrence, and stupid bugs and when you miss one.