 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Bill Wade
Guest
|
 Posted: Tue Oct 19, 2004 7:50 pm Post subject: Heap guarantees |
 |
|
| Quote: | From a thread on comp.theory:
|
Suppose iterators first, last are the range of a heap
(make_heap(first, last)), and mid is an iterator pointing into the
heap (first <= mid && mid < last).
If I increase the value of *mid, then with a "normal" heap
implementation, I can repair the heap with
push_heap(first, mid+1)
which takes O(log N) time.
AFAICS, the standard does not require the "normal" implementation,
meaning that I have no guarantee that the call will actually repair
the heap. For instance an implementation such as
push_heap(first, last)
{
if(last-first< 10) sort(first, last, greater
else
do_the_normal_push_thing(first,last);
}
seems to meet the requirements of the standard, but may not repair the
heap. Since I have to worry about this, I have to use
make_heap(first, last) to repair the heap and this takes O(N) time.
(Alternatively, I write my own heap operations, duplicating the
actual, but not guaranteed, implementation provided by my vendor's
compiler).
Would the standard be better if it required the useful behavior which
is universally implemented?
---
[ comp.std.c++ is moderated. To submit articles, try just posting with ]
[ your news-reader. If that fails, use mailto:std-c++@ncar.ucar.edu ]
[ --- Please see the FAQ before posting. --- ]
[ FAQ: http://www.jamesd.demon.co.uk/csc/faq.html ]
|
|
| Back to top |
|
 |
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
