reversed heapification?

Discussion in 'Python' started by Stefan Behnel, Mar 7, 2005.

  1. 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
     
    Stefan Behnel, Mar 7, 2005
    #1
    1. Advertising

  2. Stefan Behnel

    Kent Johnson Guest

    Stefan Behnel wrote:
    > 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.


    heapq.nlargest()
    heapq.nsmallest()
    ?

    Python 2.4 only

    Kent
     
    Kent Johnson, Mar 7, 2005
    #2
    1. Advertising

  3. Kent Johnson schrieb:
    > heapq.nlargest()
    > heapq.nsmallest()
    > ?
    >
    > Python 2.4 only


    Thanks!

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

    Stefan
     
    Stefan Behnel, Mar 7, 2005
    #3
  4. Kent Johnson wrote:
    > heapq.nlargest()
    > heapq.nsmallest()


    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
     
    Stefan Behnel, Mar 7, 2005
    #4
  5. Stefan Behnel

    Jeff Epler Guest

    Can you use something like (untested)
    class ComparisonReverser:
    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 (ComparisonReverser(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)

    iD8DBQFCLFhRJd01MZaTXX0RAuYZAKCsgFERoFijEbvsSHPFa9jByIXjVwCdEBT3
    n9/eaVmz5jxW5Uo4uDmaG8E=
    =35bo
    -----END PGP SIGNATURE-----
     
    Jeff Epler, Mar 7, 2005
    #5
  6. Stefan Behnel

    Kent Johnson Guest

    Stefan Behnel wrote:
    >
    > Kent Johnson wrote:
    >
    >> heapq.nlargest()
    >> heapq.nsmallest()

    >
    >
    > 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?


    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

    >
    > Stefan
     
    Kent Johnson, Mar 7, 2005
    #6
  7. Jeff Epler wrote:
    > Can you use something like (untested)
    > class ComparisonReverser:
    > 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 (ComparisonReverser(f(x)), i, x) as the decorated item
    > instead of (f(x), i, x)


    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
     
    Stefan Behnel, Mar 7, 2005
    #7
    1. Advertising

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

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. David Li

    the byte be reversed! why?

    David Li, Apr 24, 2005, in forum: C++
    Replies:
    7
    Views:
    483
    David Li
    Apr 24, 2005
  2. mark
    Replies:
    2
    Views:
    289
    Dave K
    Jan 3, 2004
  3. Replies:
    13
    Views:
    449
    Sion Arrowsmith
    Nov 6, 2006
  4. bit reversed order

    , Aug 17, 2007, in forum: VHDL
    Replies:
    1
    Views:
    1,521
  5. david.karr
    Replies:
    1
    Views:
    355
    david.karr
    Sep 7, 2007
Loading...

Share This Page