The Insight Journal logo

Mutable Priority Queue Container

Gelas, Arnaud, Gouaillard, Alexandre, Megason, Sean
Singapore Agency for Science Technology and Research
The Insight Journal logo

Please use this identifier to cite or link to this publication:
New: Prefer using the following doi:
Submitted by Alexandre Gouaillard on 2008-06-30.

When dealing with functional minimization, or maximization, it can sometimes be solved by a greedy algorithm. To implement greedy algorithm one needs priority queue container, i.e. get for a very low cost the lowest or highest element present in a sorted container. Whenever the priority of one element present in the queue needs to be modified, standard implementations, like \code{std::priority\_queue}, can not be applied directly. VTK has is own implementation \code{vtkPriorityQueue} which is not templated and can only be applied for \code{vtkIdType} and for the minimizing the functional. We propose here an implementation of a mutable priority queue container where element, priority, and objective (minimization or maximization) are given by template arguments. Our implementation allows to minimize or maximize a given functional, and any element can be modified, deleted at any time, and with a low cost.