Re: "Reverse" heapify

From: rossum (rossum48_at_coldmail.com)
Date: 10/17/04 

Date: Sat, 16 Oct 2004 23:12:19 +0100

On 16 Oct 2004 01:25:00 -0700, clemenr@wmin.ac.uk (Ross Clement)
wrote:

>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

A thought. When you find the first solution fill your beam with n
copies of the first solution, dead easy since there is no need to sort
with all elements identical. After that the heap is always full size.

Possible problem, what if more than one of the copies of the initial
solution survives to the end? I don't know how your code will cope
with identical solutions. Is there a dummy solution which must be
worse than all possible actual solution? That would avoid having any
duplicates surviving.

rossum 

--
The ultimate truth is that there is no Ultimate Truth
Quantcast