Minimum of a matrix in C++

Question

I have a std::vector<std::vector<type T>> matrix, I insert elements of type T to this matrix and I do some instructions by line on these elements. I need also at each iteration to delete the element with a minimum cost.

I created an std::priority_queue<Costelement, std::vector<Costelement>, Costelement::Comparekeys> Costvec; where:

 struct Costelement
{
    int row;
    int column;
    std::vector<double> cost;

    struct CompareCosts
    {
        bool operator()(const Costelement &e1, const Costelement &e2)
        {
            return (e1.cost > e2.cost);
        }
    };
};

where row and column are the position of the element in matrix having the corresponding cost. However, when I delete the element with minimum key from matrix, the positions of the elements in the corresponding row change. I used std::min_element at each iteration on matrix but this was very costly. How can we model efficiently this case?

Why is a `cost` member of a `Costelement` structure a _vector_ of `double` values? Shouldn't it be a single `double` instead? — CiaPan, Jun 08 '21 at 17:35
How does the comparison work in `e1.cost > e2.cost` for `Costelement::cost` being a vector? — CiaPan, Jun 09 '21 at 08:14

G. Sliepen · Answer 1 · 2021-06-08T17:34:03.543

A std::priority_queue by default is just a std::vector that is kept in a sorted state. It can still be expensive to insert and remove elements from the queue, and as you noticed, you would potentially need to update all of the Costelements in the queue when you insert or remove an element from matrix in order to relect the new positions. However, you can make that a bit more efficient by making the priority queue two-dimensional as well, something that looks like:

std::priority_queue<std::priority_queue<Costelement, ...>, ...> cost_matrix;

Basically, the inner priority queue sort the cost of the columns of a single row, the outer priority queue should then sort the cost of whole rows. Let's create ColumnCost and RowCost structs:

struct ColumnCost {
    int column;
    double cost;

    friend bool operator<(const ColumnCost &a, const ColumnCost &b) {
        return a.cost > b.cost;
    }
};

struct RowCost {
    int row;
    std::priority_queue<ColumnCost> columns;

    friend bool operator<(const RowCost &a, const RowCost &b) {
        return a.columns.top() > b.columns.top();
    }
};

std::priority_queue<RowCost> cost_matrix;

Now you can easily get the lowest cost element from costmatrix, which returns the RowCost which contains the lowest cost element, and then you get the ColumnCost with the lowest cost from that one:

const auto &lowest_row = cost_matrix.top();
const auto &lowest_column = lowest_row.columns.top();
int row = lowest_row.row;
int column = lowest_column.column;

When you now insert or delete an element from matrix, you insert or delete from cost_matrix in the same way. You still need to update row or column coordinates, but now it is much less work. The only thing to be aware of is that if you update add or remove an element to the priority queue of a RowCost, you need to delete and re-insert that whole row from cost_matrix to ensure the outer priority queue is kept correctly sorted.

Another possible optimization is to use a std::priority_queue to keep the rows sorted, but use std::min_element() to keep track of the minimum of each individual row. This greatly reduces the amount of memory necessary to store the cost_matrix, and you would only need to call std::min_element() to recalculate the minimum cost element of a row when you change that row.

Thank you for your response. If I use `std::priority_queue>` I cannot access the elements of the matrix — user108724, Jun 16 '21 at 09:35
Why not? The 2D priority queue contains both the row and column indices into the matrix. — G. Sliepen, Jun 16 '21 at 20:43
Silepen with priority_queue we cannot access the elements, unless we pop them in order to access to each one [link](https://stackoverflow.com/questions/4484767/how-to-iterate-over-a-priority-queue) _italic_ **bold** — user108724, Jun 17 '21 at 13:43
@user108724 Ah, that's what you mean. But why do you need to access random elements of the priority queue? Wasn't the problem just to be able to find the element with the minimum cost? That should be possible just by using `.top()` on the priority queues. If you need more than that, then indeed you cannot use `std::priority_queue` itself, then you'd either want a sorted `std::vector` or perhaps a `std::set` (but you should be able to nest those as well). — G. Sliepen, Jun 17 '21 at 20:43
yes I need to manipulate the data of each row of my matrix, not only the search for the minimum unfortunately — user108724, Jun 17 '21 at 23:17

score 0 · Answer 2 · answered Jun 08 '21 at 17:33

You may want to replace a row vector with a rope (see the rope data structure in Wikipedia).

It's a binary tree based structure, which allows quite efficient removing elements and searching for an n-th element ('indexing'), so you needn't update positions in all elements when you remove one of them.

Minimum of a matrix in C++

2 Answers2