Subject: [boost] Is there any interest in min-max heap and bounded priority queue implementations?
From: Andrea Sansottera (andrea.sansottera_at_[hidden])
Date: 2011-12-13 03:06:39
Dear Boost developers and users,
I have implemented the min-max
and a bounded priority queue container adapter. I was wondering if anyone
is interested in including this code in Boost. I have made the code
here, under the BSD license (I might switch to the Boost license if
needed). For those not familiar with min-max heaps, a min-max heap is an
implicit data structure that can be build in linear time and provides
constant time access to both the minimum and maximum elements. Other
operations require logarithmic time. Hence, they allow the efficient
implementation of double ended priority queues.
My min-max heap implementation is designed similarly to the STL heap
algorithms and consists of the following template functions:
make_minmaxheap, push_minmaxheap, popmin_minmaxheap, popmax_minmaxheap. The
bounded priority queue container adapter is built on top of the min-max
heap algorithms and its interface is similar to the STL priority_queue. The
methods of the bounded_priority_queue template class are: push, top,
bottom, pop_top, pop_bottom, size, max_size, empty. The template arguments
are the item type, the container type and the compare functor.
The code compiles and works correctly with the GNU, Intel, Clang and
Microsoft compilers. I have unit tests based on Boost.Test.
Any feedback would be appreciated.