[SciPy-dev] Question: general heap implementation versus specific?

[Thouis (Ray) Jones]

Lee Kamentsky has been working on a replacement for the watershed
image transformation in scipy (the current one isn't exactly broken,
but behaves in unexpected ways for some images).  As part of this work
he implemented heaps in cython, specific to this problem (integers, 4
entries per heap element).  I spent some time generalizing it to
arbitrary number of entries per element, with the thought that it
could be of use elsewhere in scipy.

I wonder now if that was worthwhile.  The performance cost of the
generalization isn't horrible, but not negligible, and I wonder if it
the code can actually be used elsewhere effectively.  For instance,
the recent kdTree code has a heap implementation as well, but I don't
think it could take advantage of this code (I haven't looked too
closely).

Any opinions or advice on the relative cost of generality and
simplicity versus performance?

I've attached the current heap implementation for reference.

Ray Jones
-------------- next part --------------
A non-text attachment was scrubbed...
Name: heap.pxi
Type: application/octet-stream
Size: 4593 bytes
Desc: not available
URL: <http://mail.python.org/pipermail/scipy-dev/attachments/20090302/e7eb89f7/attachment.obj>