https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62045
--- Comment #10 from Jonathan Wakely <redi at gcc dot gnu.org> --- Author: redi Date: Wed Mar 15 20:11:48 2017 New Revision: 246173 URL: https://gcc.gnu.org/viewcvs?rev=246173&root=gcc&view=rev Log: PR libstdc++/62045 fix O(N) insertion in pd_ds binary heap 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. 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: trunk/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queue_binary_heap-62045.cc Modified: trunk/libstdc++-v3/ChangeLog trunk/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp trunk/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp trunk/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queues.cc