Ross Clement
2004-10-16 08:25:00 UTC
Hi. I'm writing a program where I need to perform a beam search. I
maintain my fixed-size list of "best current solutions" in a heap,
with the "worst" solution at the top of the heap, and better solutions
lower down. I can therefore know instantly whether a new solution
should be included in my beam, as it will be better than the solution
on top of the heap (in position 0 of my array). If it is better, then
I drop the worst solution, replace it with the new one, and then
heapify() the new one down to a suitable place to rebuild my heap.
So far so good. But, the above discussion assumes that my beam is
full. When the beam is not yet full, then all new solutions will be
added to it. Effectively, I'm building a heap bit by bit. So, the
method I use is to place the new solution at the end of the array, and
then "reverse heapify" it back up to a proper position in the heap. I
expected this to be a bit tricky, but it turned out very suspiciously
easy. Basically, I look for the parent (at position (n-1)/2 where n
starts at 0 and division is integer), and see if the new node and the
parent should be swapped. If so, I swap them, and then continue
"reverse heapifying" from the parent. The code is:
void reverseHeapify( node *sink[], int start )
{
int parent;
node *temp;
if ( start == 0 )
{
return;
}
parent = ( start - 1 ) / 2;
if ( better( sink[parent], sink[start] ))
{
temp = sink[parent];
sink[parent] = sink[start];
sink[start] = temp;
reverseHeapify( sink, parent );
}
}
As I said, this does seem *very* easy. So much so that as far as I can
see, it should be the standard way of building a heap rather than the
much more complex heapify(left), heapify(right), pushdown(current). Is
there something wrong in what I've done? Certainly, it's O(log n) to
add a new element to a heap, and therefore O(n log n) to build a heap
of n elements, which could be done in place by starting with a heap of
1, 'adding' the next element by incrementing an index, reverse
heapifying it, 'adding' the next one.
Would this be slower than the standard method? If so, why?
Note: I'm not confidence my code is 100% debugged. I wrote the code
(including a standard heapify) in one go, and it immediately worked.
Past experience suggests that hidden bugs not exposed in my test case
are a far more likely possibility than the possibility that I wrote
that much code without a single bug.
Cheers,
Ross-c
maintain my fixed-size list of "best current solutions" in a heap,
with the "worst" solution at the top of the heap, and better solutions
lower down. I can therefore know instantly whether a new solution
should be included in my beam, as it will be better than the solution
on top of the heap (in position 0 of my array). If it is better, then
I drop the worst solution, replace it with the new one, and then
heapify() the new one down to a suitable place to rebuild my heap.
So far so good. But, the above discussion assumes that my beam is
full. When the beam is not yet full, then all new solutions will be
added to it. Effectively, I'm building a heap bit by bit. So, the
method I use is to place the new solution at the end of the array, and
then "reverse heapify" it back up to a proper position in the heap. I
expected this to be a bit tricky, but it turned out very suspiciously
easy. Basically, I look for the parent (at position (n-1)/2 where n
starts at 0 and division is integer), and see if the new node and the
parent should be swapped. If so, I swap them, and then continue
"reverse heapifying" from the parent. The code is:
void reverseHeapify( node *sink[], int start )
{
int parent;
node *temp;
if ( start == 0 )
{
return;
}
parent = ( start - 1 ) / 2;
if ( better( sink[parent], sink[start] ))
{
temp = sink[parent];
sink[parent] = sink[start];
sink[start] = temp;
reverseHeapify( sink, parent );
}
}
As I said, this does seem *very* easy. So much so that as far as I can
see, it should be the standard way of building a heap rather than the
much more complex heapify(left), heapify(right), pushdown(current). Is
there something wrong in what I've done? Certainly, it's O(log n) to
add a new element to a heap, and therefore O(n log n) to build a heap
of n elements, which could be done in place by starting with a heap of
1, 'adding' the next element by incrementing an index, reverse
heapifying it, 'adding' the next one.
Would this be slower than the standard method? If so, why?
Note: I'm not confidence my code is 100% debugged. I wrote the code
(including a standard heapify) in one go, and it immediately worked.
Past experience suggests that hidden bugs not exposed in my test case
are a far more likely possibility than the possibility that I wrote
that much code without a single bug.
Cheers,
Ross-c