This is the mail archive of the
gcc-bugs@gcc.gnu.org
mailing list for the GCC project.
[Bug libstdc++/61217] New: pop_heap can't guarantee At most 2 * log(last - first) comparisons
- From: "kan.liu.229 at gmail dot com" <gcc-bugzilla at gcc dot gnu dot org>
- To: gcc-bugs at gcc dot gnu dot org
- Date: Sun, 18 May 2014 15:22:16 +0000
- Subject: [Bug libstdc++/61217] New: pop_heap can't guarantee At most 2 * log(last - first) comparisons
- Auto-submitted: auto-generated
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61217
Bug ID: 61217
Summary: pop_heap can't guarantee At most 2 * log(last - first)
comparisons
Product: gcc
Version: 4.9.0
Status: UNCONFIRMED
Severity: minor
Priority: P3
Component: libstdc++
Assignee: unassigned at gcc dot gnu.org
Reporter: kan.liu.229 at gmail dot com
pop_heap uses __adjust_heap to percolate down the hole.
Inside __adjust_heap, it uses __value stores the value where was in position
__result(__last). After percolating down the hole, it uses __push_heap to push
back the __value. Process of percolatiing down takes 2 * logN comparasion, and
__push_heap takes another 2 * logN, 4 * logN in total, which excceed the
requirement "2 * log(last - first) comparisons" of standard.