Re: [PATCH] binary heap implementation

Abhijit Menon-Sen <ams(at)2ndQuadrant(dot)com> writes:
>> While I'm thinking about it, why are the fields of a binaryheap_node
>> called "key" and "value"? That implies a semantics not actually used
>> here. Maybe "value1" and "value2" instead?

> Yes, I discussed this with Andres earlier (and considered ptr and value
> or p1 and p2), but decided to wait for others to comment on the naming.
> I have no problem with value1 and value2, though I'd very slightly
> prefer d1 and d2 (d for Datum) now.

d1/d2 would be fine with me.

BTW, I probably missed some context upthread, but why do we have two
fields at all? At least for the purposes of nodeMergeAppend, it
would make a lot more sense for the binaryheap elements to be just
single Datums, without all the redundant pointers to the MergeAppend
node. The need to get at the comparison support info could be handled
much more elegantly than that by providing a "void *" passthrough arg.
That is, the heap creation function becomes

binaryheap *binaryheap_allocate(size_t capacity,
binaryheap_comparator compare,
void *passthrough);

and the comparator signature becomes

typedef int (*binaryheap_comparator) (Datum a, Datum b, void *passthrough);

For nodeMergeAppend, the Datums would be the slot indexes and the
passthrough pointer could point to the MergeAppend node.

This would make equal sense in a lot of other contexts, such as if you
wanted a heap composed of tuples -- the info to compare tuples could be
handled via the passthrough argument, rather than doubling the size of
the heap in order to put that pointer into each heap element. If you
have no use for the passthrough arg in a particular usage, just pass
NULL.

regards, tom lane