d******i
发帖数: 7160 | 1 背景是想做k个最小值的维护，用了k-size的大顶堆。
本来逻辑上是顺畅的:
新元素比堆顶大，直接pass；
o/w替换堆顶，做个ShiftDown维护。
按说复杂度log2(k)吧，撑死找条path走到底。
代码当然可以写，但还是指望STL堆函数给点捷径，结果很失望。
貌似只能先pop_heap清掉，再入尾后push_heap，非得整理两次不可,代码如下：
//remove the old top one, since no longer qualify
pop_heap(vmo1.begin(),vmo1.end(),classcmp);
vmo1.pop_back();
//insert the new one, since must qualify
vmo1.push_back(*ivmo); //*ivmo是比堆顶小的新元素
push_heap(vmo1.begin(),vmo1.end(),classcmp);
复杂度一下子double了，成了2*log2(k)。
当然可以用复杂度k的make_heap，就不提了。
有没有利用STL现有堆函数实现这个ShiftDown的简单办法(只走一次path)？
请指教。
谢谢！ | f*******n
发帖数: 12623 | | d******i
发帖数: 7160 | 3 ?
【在 f*******n 的大作中提到】
: 都是O(log k)。
| d****i
发帖数: 4809 | 4 我想楼上指的是log(K)和2log(K)的复杂度是一样的，都是O(log(K))吧。
【在 d******i 的大作中提到】
: ?
| d******i
发帖数: 7160 | 5 这个我自然明白。
我说的本来就是"复杂度double成2*log(k)",没说升级成O(k)啊。
所以这结果就该知足？
OP说了，偶不明白的是为什么逻辑如此直接的一遍shiftdown
靠stl自身的函数做不到，
非要做两遍，弄成log(k)+log(k)
而且得收回刚才的话“代码当然可以写”，因为不知道这个堆底层的内存布局，
所以没法手动shift。
【在 d****i 的大作中提到】
: 我想楼上指的是log(K)和2log(K)的复杂度是一样的，都是O(log(K))吧。
| t****t
发帖数: 6806 | 6 heap.back()=new_element;
pop_heap(heap.begin(), heap.end());
【在 d******i 的大作中提到】
: 背景是想做k个最小值的维护，用了k-size的大顶堆。
: 本来逻辑上是顺畅的:
: 新元素比堆顶大，直接pass；
: o/w替换堆顶，做个ShiftDown维护。
: 按说复杂度log2(k)吧，撑死找条path走到底。
: 代码当然可以写，但还是指望STL堆函数给点捷径，结果很失望。
: 貌似只能先pop_heap清掉，再入尾后push_heap，非得整理两次不可,代码如下：
: //remove the old top one, since no longer qualify
: pop_heap(vmo1.begin(),vmo1.end(),classcmp);
: vmo1.pop_back();
| t****t
发帖数: 6806 | 7 note: you need to make sure the heap has 1 more element than you want.
【在 t****t 的大作中提到】
: heap.back()=new_element;
: pop_heap(heap.begin(), heap.end());
| t****t
发帖数: 6806 | 8 also remember to compare first...i.e.
if (new_element>heap.front()) {
heap.back()=new_element;
pop_heap(heap.begin(), heap.end());
}
【在 t****t 的大作中提到】
: note: you need to make sure the heap has 1 more element than you want.
| d******i
发帖数: 7160 | 9 Actually I tried some similar before like this.
None of them works. b/c pop_heap ask for the whole range it operates (
defined by the parameter) is a PRE-EXISTING heap.
But the newly assigned back "heap.back()" apparantly breaks that pre-
existing heap-order. As thus, the following pop-heap won't work correctly,
though it will still do something :(
It's not hard to prove, and I did have verified.
【在 t****t 的大作中提到】
: also remember to compare first...i.e.
: if (new_element>heap.front()) {
: heap.back()=new_element;
: pop_heap(heap.begin(), heap.end());
: }
| t****t
发帖数: 6806 | 10 yes the document says it require x.begin(), x.end() is a heap. but in fact
it only requires x.begin(), x.end()-1 is a heap. that's the reason i said
you need 1 more element than you wanted.
think about it.
【在 d******i 的大作中提到】
: Actually I tried some similar before like this.
: None of them works. b/c pop_heap ask for the whole range it operates (
: defined by the parameter) is a PRE-EXISTING heap.
: But the newly assigned back "heap.back()" apparantly breaks that pre-
: existing heap-order. As thus, the following pop-heap won't work correctly,
: though it will still do something :(
: It's not hard to prove, and I did have verified.
| | | d******i
发帖数: 7160 | 11 i think you definitely want the pop_heap()
to cover the newly inserted element.
but the newly inserted element - back() HAS ALREADY BROKEN the heap-order.
Then the pop-heap won't work correctly.
Once again, pop-heap requires all the elements conforms the heap-order. It
initially did. But after you changed the back(), it wouldn't.
It's not a proble of one more element or not. It's a problem of WHETHER to
include the new element into the pop-heap or not. Absolutely you need. But
then the pop-heap won't work. That is it.
【在 t****t 的大作中提到】
: yes the document says it require x.begin(), x.end() is a heap. but in fact
: it only requires x.begin(), x.end()-1 is a heap. that's the reason i said
: you need 1 more element than you wanted.
: think about it.
| t****t
发帖数: 6806 | 12 if you think how heap works, you know you don't need the last element to be
heap-compatible. the last element is swapped to first, and sifted down. it
can be any element.
【在 d******i 的大作中提到】
: i think you definitely want the pop_heap()
: to cover the newly inserted element.
: but the newly inserted element - back() HAS ALREADY BROKEN the heap-order.
: Then the pop-heap won't work correctly.
: Once again, pop-heap requires all the elements conforms the heap-order. It
: initially did. But after you changed the back(), it wouldn't.
: It's not a proble of one more element or not. It's a problem of WHETHER to
: include the new element into the pop-heap or not. Absolutely you need. But
: then the pop-heap won't work. That is it.
| d******i
发帖数: 7160 | 13 Please note we are talking about how pop_heap asks, not how we think or
understand. It's not our problem why STL's pop_heap function asks that. But
unfortuantely it has such a requirement. Then we'll suffer if we have to
rely on the STL's heap function.
If you still cannot get it, compile the code you give and verify it. Like I
said, I tried and it does not work. I think the reason has been quite
sufficiently clarified.
Just run your code to justify yourself, like what I did. It's not a place
just by talking, but by coding.
be
【在 t****t 的大作中提到】
: if you think how heap works, you know you don't need the last element to be
: heap-compatible. the last element is swapped to first, and sifted down. it
: can be any element.
| t****t
发帖数: 6806 | 14 direct stdout and stderr to different files and try yourself.
int main()
{
srand(0);
vector x(5, 1.0);
make_heap(x.begin(), x.end());
for (int i=0; i<10000; i++) {
double n=double(rand())/RAND_MAX;
if (n
x.back()=n;
pop_heap(x.begin(), x.end());
}
cout<
}
for (size_t i=0; i
cerr<
}
cerr<<"\n";
}
But
I
【在 d******i 的大作中提到】
: Please note we are talking about how pop_heap asks, not how we think or
: understand. It's not our problem why STL's pop_heap function asks that. But
: unfortuantely it has such a requirement. Then we'll suffer if we have to
: rely on the STL's heap function.
: If you still cannot get it, compile the code you give and verify it. Like I
: said, I tried and it does not work. I think the reason has been quite
: sufficiently clarified.
: Just run your code to justify yourself, like what I did. It's not a place
: just by talking, but by coding.
:
| t****t
发帖数: 6806 | 15 of course, if you are striving for standard conformance, you can write your
own heap implementation. but in the heart you know it's correct and it's
basically the same implementation.
But
I
【在 d******i 的大作中提到】
: Please note we are talking about how pop_heap asks, not how we think or
: understand. It's not our problem why STL's pop_heap function asks that. But
: unfortuantely it has such a requirement. Then we'll suffer if we have to
: rely on the STL's heap function.
: If you still cannot get it, compile the code you give and verify it. Like I
: said, I tried and it does not work. I think the reason has been quite
: sufficiently clarified.
: Just run your code to justify yourself, like what I did. It's not a place
: just by talking, but by coding.
:
| d******i
发帖数: 7160 | 16 0.383892
0.771111
0.910123
0.424635
0.085757
0.989868
0.610736
0.261818
0.727836
0.690664
0.424635 0.261818 0.383892 0.085757
Press any key to continue
please explain if the first 3 is really the minimal 3.
This is my third run of your code.
I modified it to the following to make it compiled on VC6:
#include XXX
void testK()
{
srand(time(NULL));
vector x(5, 1.0);
make_heap(x.begin(), x.end());
for (int i=0; i<10; i++) {
double n=double(rand())/RAND_MAX;
if (n
x.back()=n;
pop_heap(x.begin(), x.end());
}
cout<
}
for (i=0; i
cerr<
}
cerr<<"\n";
}
int main(int argc, char* argv[])
{
testK();
return 0;
}
Amny thanks to ur work, But as I said, it does not work.
【在 t****t 的大作中提到】
: direct stdout and stderr to different files and try yourself.
: int main()
: {
: srand(0);
: vector x(5, 1.0);
: make_heap(x.begin(), x.end());
: for (int i=0; i<10000; i++) {
: double n=double(rand())/RAND_MAX;
: if (n: x.back()=n;
| t****t
发帖数: 6806 | 17 what's wrong with the result?
of course, the heap itself is not sorted, and it's never meant to be. but it
contains the 4 minimum numbers out of 10, which is exactly what you wanted.
【在 d******i 的大作中提到】
: 0.383892
: 0.771111
: 0.910123
: 0.424635
: 0.085757
: 0.989868
: 0.610736
: 0.261818
: 0.727836
: 0.690664
| t****t
发帖数: 6806 | 18 and i declared a 5-element heap, output 4. can't you read?
【在 d******i 的大作中提到】
: 0.383892
: 0.771111
: 0.910123
: 0.424635
: 0.085757
: 0.989868
: 0.610736
: 0.261818
: 0.727836
: 0.690664
| d******i
发帖数: 7160 | 19 just check. u r right.
the MSDN's really confusing about the pop_heap:
"
pop_heap
template
void pop_heap(RanIt first, RanIt last);
template
void pop_heap(RanIt first, RanIt last, Pred pr);
The first template function reorders the sequence designated by iterators in
the range [first, last) to form a new heap, ordered by operator< and
designated by iterators in the range [first, last - 1), leaving the original
element at *first subsequently at *(last - 1). The original sequence must
designate an existing heap, also ordered by operator<. Thus, first != last
must be true and *(last - 1) is the element to remove from (pop off) the
heap.
The function evaluates the ordering predicate X < Y ceil(2 * log(last -
first)) times, at most.
The second template function behaves the same, except that it replaces
operator<(X, Y) with pr(X, Y).
Sample programs: heap and heap (predicate version).
"
specially on this sentence:
"The original sequence must designate an existing heap".
I think the original refers to the range [first,last-1)
thanks for you correction :)
【在 t****t 的大作中提到】
: and i declared a 5-element heap, output 4. can't you read?
| j*a
发帖数: 14423 | 20 你终于写code啦！
【在 t****t 的大作中提到】
: direct stdout and stderr to different files and try yourself.
: int main()
: {
: srand(0);
: vector x(5, 1.0);
: make_heap(x.begin(), x.end());
: for (int i=0; i<10000; i++) {
: double n=double(rand())/RAND_MAX;
: if (n: x.back()=n;
| | | t****t
发帖数: 6806 | 21 this is not a test or interview question, so i am willing to write code.
【在 j*a 的大作中提到】
: 你终于写code啦！
| t****t
发帖数: 6806 | 22 actually, the standard does say [first, last) must be a heap, but it also
says "Swaps the value in the location first with the value in the location
last - 1 and makes [first,last - 1) into a heap." and you know last[-1] (
the last element of a heap) is some arbitrary number anyway, be it a part of
heap or not.
when you know what is heap, you can make some creative use of existing code.
although purists like me will write my own code in this case.
BTW you don't need to read MSDN when you can read standard itself. and VC6
is notorious anyway.
in
【在 d******i 的大作中提到】
: just check. u r right.
: the MSDN's really confusing about the pop_heap:
: "
: pop_heap
: template
: void pop_heap(RanIt first, RanIt last);
: template
: void pop_heap(RanIt first, RanIt last, Pred pr);
: The first template function reorders the sequence designated by iterators in
: the range [first, last) to form a new heap, ordered by operator< and
| d******i
发帖数: 7160 | 23 got it.
thx for ur advice.
of
code.
【在 t****t 的大作中提到】
: actually, the standard does say [first, last) must be a heap, but it also
: says "Swaps the value in the location first with the value in the location
: last - 1 and makes [first,last - 1) into a heap." and you know last[-1] (
: the last element of a heap) is some arbitrary number anyway, be it a part of
: heap or not.
: when you know what is heap, you can make some creative use of existing code.
: although purists like me will write my own code in this case.
: BTW you don't need to read MSDN when you can read standard itself. and VC6
: is notorious anyway.
:
| d******i
发帖数: 7160 | 24 sorry又来了，就是想把事情想明白。
下面的code在vc6没问题。
可是放在vs2008下就出错。
应该是断在了这句(当i=4时)：
pop_heap(x.begin(), x.end());
完整代码如下：
#includeXXX
void testK2()
{
srand(time(NULL));
vector x(5, 1.0);
make_heap(x.begin(), x.end());
for (int i=0; i<100; i++) {
double n=double(rand())/RAND_MAX;
if (n
x.back()=n;
pop_heap(x.begin(), x.end());
}
cout<
}
for (size_t i=0; i
cerr<
}
cerr<<"\n";
}
int main(int argc, char* argv[])
{
testK2();
return 0;
}
出错信息如下:
> testHeap.exe!std::_Debug_message(const wchar_t * message=0x004e4eb0,
const wchar_t * file=0x004e4ad0, unsigned int line=1936) 行24 C++
testHeap.exe!std::_Debug_heap
allocator > >(std::_Vector_iterator >
_First=0.75283059175389877, std::_Vector_iterator
double> > _Last=-2.5301711256524607e-098) 行1936 + 0x14 字节 C++
testHeap.exe!std::pop_heap
double> > >(std::_Vector_iterator > _First=0.
76918851283303324, std::_Vector_iterator > _
Last=-2.5301711256524607e-098) 行2094 + 0x4d 字节 C++
挺对的程序，咋在VS2008下面就出错呢？
【在 t****t 的大作中提到】
: direct stdout and stderr to different files and try yourself.
: int main()
: {
: srand(0);
: vector x(5, 1.0);
: make_heap(x.begin(), x.end());
: for (int i=0; i<10000; i++) {
: double n=double(rand())/RAND_MAX;
: if (n: x.back()=n;
| d******i
发帖数: 7160 | 25 anyone knows?
【在 d******i 的大作中提到】
: sorry又来了，就是想把事情想明白。
: 下面的code在vc6没问题。
: 可是放在vs2008下就出错。
: 应该是断在了这句(当i=4时)：
: pop_heap(x.begin(), x.end());
: 完整代码如下：
: #includeXXX
: void testK2()
: {
: srand(time(NULL));
| t****t
发帖数: 6806 | 26 apparently, some implementation checked the consistency of heap before pop_
heap(). that's the reason of purist just write the code again.
【在 d******i 的大作中提到】
: anyone knows?
| d******i
发帖数: 7160 | 27 Hehe,问题又回来了不是？
pop_heap()要求作用范围已然成堆，对不？
【在 t****t 的大作中提到】
: apparently, some implementation checked the consistency of heap before pop_
: heap(). that's the reason of purist just write the code again.
| t****t
发帖数: 6806 | 28 yeah, i said that already. not sure why you bring this up again.
【在 d******i 的大作中提到】
: Hehe,问题又回来了不是？
: pop_heap()要求作用范围已然成堆，对不？
| d******i
发帖数: 7160 | 29 Because ur solution didn't comply to the requirement of what pop_heap asks
in VS2008, though in VC6 such a check is not imposed (and the MSDN for pop_
heap of VC6 is not precise, either)
My question is very clear in OP - seeking a solution with only one
invocation of pop_heap, not push_heap then pop_heap. I tested this two-pass
solution is correct on VC6 and VS2008.
But it appears like there's no one-pass solution (only with pop_heap) that
can survive VS2008, like the one you suggested;
【在 t****t 的大作中提到】
: yeah, i said that already. not sure why you bring this up again.
| t****t
发帖数: 6806 | 30 我不是说得很清楚, 要我写就自己重写一遍吗? 不知道你来来回回的纠结什么...
pass
【在 d******i 的大作中提到】
: Because ur solution didn't comply to the requirement of what pop_heap asks
: in VS2008, though in VC6 such a check is not imposed (and the MSDN for pop_
: heap of VC6 is not precise, either)
: My question is very clear in OP - seeking a solution with only one
: invocation of pop_heap, not push_heap then pop_heap. I tested this two-pass
: solution is correct on VC6 and VS2008.
: But it appears like there's no one-pass solution (only with pop_heap) that
: can survive VS2008, like the one you suggested;
|
|
