search

t-lutz / ParallelSTL

Implementation of n3554, a proposal to include parallelized versions of the STL algorithms into the C++ standard.
25 stars 6 forks source link

Is_heap implementation is flawed in certain cases #22

Open Syntaf opened 8 years ago

Syntaf commented 8 years ago

Correct me if I'm wrong, but I don't think the parallel is_heap will work. I can't actually compile the code to test it due to some weird constexpr errors in execution_policy, but here's what I believe is wrong:

Say you have the heap: 9 8 6 7 4 5 2 0 3 1 , which when visualized looks like img

Now say you call parallelized is_heap, and your heap is split into 4 separate partitions. These become

9 8 6 7 4 5 2 0 3 1

The problem is that 2 0 3 is not a max heap, but the algorithm will call std::is_heap on that range. the partitions are treating the beginning part as the head node, which is wrong in this case. The first two partitions got lucky because they chose a node which happened to have children, but in the case of a non-complete heap tree this algorithm would fail.

t-lutz commented 8 years ago

You are right, the implementation is incorrect. Most of the algorithms are not fully implemented, this repository contains a skeleton implementation to validate the API from the proposal. The algorithms which are implemented have unit tests in test, every algorithm which does not have a test probably hasn't been implemented (std::is_heap doesn't have a unit test).

You are very welcome to submit a parallel implementation to this repository if you have one.