reversed heapification?

[Stefan Behnel]

Hi!

I need a general-purpose best-k sorting algorithm and I'd like to use heapq
for that (heapify + heappop*k). The problem is that heapify and heappop do not
support the "reverse" keyword as known from sorted() and list.sort(). While
the decorate-sort-undecorate pattern allows me to replace the "key" option, I
do not see an obvious way to have heapq work in a reverse way without making
assumptions on the data.

Any ideas?

Stefan

[Kent Johnson]

Re: reversed heapification?

Stefan Behnel wrote:[color=blue]
> Hi!
>
> I need a general-purpose best-k sorting algorithm and I'd like to use heapq
> for that (heapify + heappop*k). The problem is that heapify and heappop
> do not
> support the "reverse" keyword as known from sorted() and list.sort(). While
> the decorate-sort-undecorate pattern allows me to replace the "key"
> option, I
> do not see an obvious way to have heapq work in a reverse way without
> making
> assumptions on the data.[/color]

heapq.nlargest( )
heapq.nsmallest ()
?

Python 2.4 only

Kent

[Stefan Behnel]

Re: reversed heapification?


Kent Johnson schrieb:[color=blue]
> heapq.nlargest( )
> heapq.nsmallest ()
> ?
>
> Python 2.4 only[/color]

Thanks!

Those are *very* well hidden in the documentation. Maybe I already read that
page too often...

Stefan

[Stefan Behnel]

Re: reversed heapification?


Kent Johnson wrote:[color=blue]
> heapq.nlargest( )
> heapq.nsmallest ()[/color]

On second thought, that doesn't actually get me very far. I do not know in
advance how many I must select since I need to remove duplicates *after*
sorting (they are not necessarily 'duplicate' enough to fall into the same
sort bucket). What I'd like to do is heapify and then create an iterator for
the result. But since heapify doesn't support "reverse" ...

Any other ideas?

Stefan

[Jeff Epler]

Re: reversed heapification?

Can you use something like (untested)
class ComparisonRever ser:
def __init__(self, s): self.s = s
def __cmp__(self, o): return cmp(o, self.s)
def __lt__... # or whichever operation hashes use
then use (ComparisonReve rser(f(x)), i, x) as the decorated item
instead of (f(x), i, x)

Jeff

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.2.1 (GNU/Linux)

iD8DBQFCLFhRJd0 1MZaTXX0RAuYZAK CsgFERoFijEbvsS HPFa9jByIXjVwCd EBT3
n9/eaVmz5jxW5Uo4uD maG8E=
=35bo
-----END PGP SIGNATURE-----

[Kent Johnson]

Re: reversed heapification?

Stefan Behnel wrote:[color=blue]
>
> Kent Johnson wrote:
>[color=green]
>> heapq.nlargest( )
>> heapq.nsmallest ()[/color]
>
>
> On second thought, that doesn't actually get me very far. I do not know
> in advance how many I must select since I need to remove duplicates
> *after* sorting (they are not necessarily 'duplicate' enough to fall
> into the same sort bucket). What I'd like to do is heapify and then
> create an iterator for the result. But since heapify doesn't support
> "reverse" ...
>
> Any other ideas?[/color]

Wrap your data in a class that defines __cmp__ as the inverse of __cmp__ on the underlying data,
then use heapq?
Just sort the list?

Kent
[color=blue]
>
> Stefan[/color]

[Stefan Behnel]

Re: reversed heapification?

Jeff Epler wrote:[color=blue]
> Can you use something like (untested)
> class ComparisonRever ser:
> def __init__(self, s): self.s = s
> def __cmp__(self, o): return cmp(o, self.s)
> def __lt__... # or whichever operation hashes use
> then use (ComparisonReve rser(f(x)), i, x) as the decorated item
> instead of (f(x), i, x)[/color]

Thanks!

That *was* untested ;). To avoid infinite recusion (and other bizarre errors),
you'd have to compare "o.s" and "self.s".

Heapq uses "<=" internally for all comparisons, so it's enough to implement
the __le__ method:

def __le__(self, other): return other.s <= self.s

I actually looked at the C-implementation of heapq in 2.4 and saw that it even
provides distinct implementations for min-heaps and max-heaps. It would be
sooooo convinient if both of them became part of the module...

Stefan