Double-Ended Heaps

  • Thread starter Scott David Daniels
  • Start date
B

Bryan Olson

Scott said:
I've just put together a Double-Ended Heap package.
Of course I'd love comments.

http://members.dsl-only.net/~daniels/deheap.html

I think there's a typo in:

Note that any change to the contents of a DeHeap (and
therefore a DeHeap2) any re-arrange the indices of a
number of entries in the DeHeap.

A useful Python class will follow Python convention, where
relevant convention exists. In this case that means optionally
passing the ordering relation; look at sort() and sorted().

Adopting the convention will raises another issue: distinct
objects can compare as equal, so the DeHeap2 operations that
find items by value will be at least under-defined, and maybe
even broken. There are several ways to solve the problem, and
I don't know of Python convention as to which to choose.
 
S

Scott David Daniels

Bryan said:
Note that any change to the contents of a DeHeap (and
therefore a DeHeap2) any re-arrange the indices of a
number of entries in the DeHeap.

Yup, thanks (I'll tweak it tomorrow).
A useful Python class will follow Python convention, where
relevant convention exists. In this case that means optionally
passing the ordering relation; look at sort() and sorted().

That will be built from these. I have a little prototype,
but no tests yet.
Adopting the convention will raises another issue: distinct
objects can compare as equal, so the DeHeap2 operations that
find items by value will be at least under-defined, and maybe
even broken.
Actually, the issue already exists for elements which define
their own __lt__ function. The rule I will use is that you have
told the DeHeap to delete some member equal to the given value.

--Scott David Daniels
(e-mail address removed)
 
S

Scott David Daniels

Bryan said:
I think there's a typo in:

Note that any change to the contents of a DeHeap (and
therefore a DeHeap2) any re-arrange the indices of a
number of entries in the DeHeap.

A useful Python class will follow Python convention, where
relevant convention exists. In this case that means optionally
passing the ordering relation; look at sort() and sorted().

Adopting the convention will raises another issue: distinct
objects can compare as equal, so the DeHeap2 operations that
find items by value will be at least under-defined, and maybe
even broken. There are several ways to solve the problem, and
I don't know of Python convention as to which to choose.
OK, I've a new version out there.

deheap.deheap(iterable=(), key=None, sequence=False)

is a factory function making an appropriate instance.
The testing is not all that thorough on the sequence=True
classes (where even pop can use an index), but I suspect it
all works (famous last words).

--Scott David Daniels
(e-mail address removed)
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top