https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62045
--- Comment #12 from Jonathan Wakely <redi at gcc dot gnu.org> --- Author: redi Date: Tue Mar 28 17:18:37 2017 New Revision: 246548 URL: https://gcc.gnu.org/viewcvs?rev=246548&root=gcc&view=rev Log: PR libstdc++/62045 fix O(N) insertion in pd_ds binary heap Backport from mainline 2017-03-15 Xi Ruoyao <r...@stu.xidian.edu.cn> PR libstdc++/62045 * include/ext/pb_ds/qdetail/binary_heap_/binary_heap_.hpp (is_heap): Remove. (push_heap): Remove the wrong checking using is_heap. (make_heap): Remove the assertion using is_heap. * include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp (modify): Ditto. (resize_for_insert_if_needed): Add PB_DS_ASSERT_VALID after calling make_heap. Backport from mainline 2017-03-15 Jonathan Wakely <jwak...@redhat.com> PR libstdc++/62045 * testsuite/ext/pb_ds/regression/priority_queue_binary_heap-62045.cc: New test. * testsuite/ext/pb_ds/regression/priority_queues.cc: Fix copy&paste error in comment. Added: branches/gcc-6-branch/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queue_binary_heap-62045.cc Modified: branches/gcc-6-branch/libstdc++-v3/ChangeLog branches/gcc-6-branch/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp branches/gcc-6-branch/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp branches/gcc-6-branch/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queues.cc
