https://gcc.gnu.org/bugzilla/show_bug.cgi?id=62045
--- Comment #14 from Jonathan Wakely <redi at gcc dot gnu.org> --- Author: redi Date: Wed May 17 17:18:14 2017 New Revision: 248164 URL: https://gcc.gnu.org/viewcvs?rev=248164&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/detail/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-5-branch/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queue_binary_heap-62045.cc Modified: branches/gcc-5-branch/libstdc++-v3/ChangeLog branches/gcc-5-branch/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp branches/gcc-5-branch/libstdc++-v3/include/ext/pb_ds/detail/binary_heap_/insert_fn_imps.hpp branches/gcc-5-branch/libstdc++-v3/testsuite/ext/pb_ds/regression/priority_queues.cc
