Unexpected behaviour of self implemented priority queue using min heap

Question

I implemented a priority queue using a min heap in c++; here I use zero based indexing in the vector used; so for example the left and right nodes of index 5 would be (2 * 5 + 1) and (2 * 5 + 2); I use recursive functions like swim and sink (typical);

here's the c++ code:

#include <iostream>
#include <vector>

using namespace std;

template <class t>
class priorityqueue
{
private:
    vector<t> vec;

    inline static void swap(t *x, t *y)
    {
        t temp = *x;
        *x = *y;
        *y = temp;
    }

    inline static size_t left(size_t i) { return (i << 1) + 1; }

    inline static size_t right(size_t i) { return (i << 1) + 2; }

    inline static size_t up(size_t i) { return (i - 1) >> 1; }

    inline bool validindex(size_t i) { return i < vec.size(); }

    inline void swim(size_t i)
    {
        if (i == 0)
            return;
        size_t up_ = up(i);
        if (vec[i] < vec[up_])
        {
            swap(&vec[i], &vec[up_]);
            swim(up_);
        }
    }

    inline void sink(size_t i)
    {
        size_t left_ = left(i), right_ = right(i);
        if (!validindex(left_))
        {
            return;
        }
        if (!validindex(right_))
        {
            if (vec[i] > vec[left_])
            {
                swap(&vec[i], &vec[left_]);
                sink(left_);
            }
            return;
        }
        if (vec[i] < vec[left_])
        {
            if (vec[i] < vec[right_])
            {
                return;
            }
            swap(&vec[i], &vec[right_]);
            sink(right_);
        }
        else
        {
            if (vec[i] < vec[right_])
            {
                swap(&vec[i], &vec[left_]);
                sink(left_);
            }
            else
            {
                if (vec[left_] < vec[right_])
                {
                    swap(&vec[i], &vec[left_]);
                    sink(left_);
                }
                else
                {
                    swap(&vec[i], &vec[right_]);
                    sink(right_);
                }
            }
        }
    }

public:
    size_t size() { return vec.size(); }

    bool empty() { return size() == 0; }

    void push(t elem)
    {
        vec.push_back(elem);
        swim(vec.size() - 1);
    }

    t peek()
    {
        return vec[0];
    }

    t pop()
    {
        t elem = vec[0];
        t last = vec[vec.size() - 1];
        swap(&last, &elem);
        vec.pop_back();
        sink(0);
        return elem;
    }
};

int main()
{
    priorityqueue<int> pq;
    pq.push(3);
    pq.push(1);
    pq.push(4);
    pq.push(1);
    pq.push(5);
    pq.push(9);
    pq.push(2);
    pq.push(6);
    pq.push(5);
    pq.push(3);
    while (!pq.empty())
    {
        cout << pq.pop() << " ";
    }
}

the result it gives is :

(base) miglanigursimar@Miglanis-MacBook-Pro priorityqueue % ./a.out 
5 5 6 4 9 3 3 2 1 1 %

whereas it should print the first ten digits of pi in ascending order.

Answer 1

One big issue is in the pop function.

#include <iostream>
#include <vector>

using namespace std;

template <class t>
class priorityqueue
{
private:
    vector<t> vec;

    inline static void swap(t *x, t *y)   // Why? Use std::swap instead.
    {
        t temp = *x;
        *x = *y;
        *y = temp;
    }

// [...]
  
    t pop()
    {
        t elem = vec[0];
        t last = vec[vec.size() - 1];
        swap(&last, &elem);             // <---------
        vec.pop_back();
        sink(0);
        return elem;
    }
};
// [...]

There, last and elem are local copies of the two elements of the vector, swapping them doesn't change the original ones.

The OP should either declare those as references or copy the first and then directly swap the elements of the vector.