473,324 Members | 1,856 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,324 software developers and data experts.

reversed heapification?

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
Jul 18 '05 #1
6 1592
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
Jul 18 '05 #2

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
Jul 18 '05 #3

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
Jul 18 '05 #4
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)

iD8DBQFCLFhRJd01MZaTXX0RAuYZAKCsgFERoFijEbvsSHPFa9 jByIXjVwCdEBT3
n9/eaVmz5jxW5Uo4uDmaG8E=
=35bo
-----END PGP SIGNATURE-----

Jul 18 '05 #5
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

Jul 18 '05 #6
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
Jul 18 '05 #7

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: mark | last post by:
I am looking at the format used by root.geometry(). The string returned from root.geometry() is "%dx%d+%d+%d". Is there a quick and painless way to extract the values from that string (i.e.,...
19
by: Canon EOS | last post by:
Hi, I am really new in .net and pocket PC development. My background are purely C/C++/VC++. Have developed on Mobile Java for a year and felt completely insecure with it because all codes can...
1
by: David Li | last post by:
I use VC++6.0 to code. When I defined: struct Prop { UINT32 obj;} , and I read bytes from file: { char buf); fread(buf,4); } then I use (Prop*)buf to set m_prop which is declared as Prop;(m_prop...
5
by: John B | last post by:
Hello I want to have a number of controls all docked left next to each other. When I try the code below, the items are reversed with the last button nearest the left instead of the first. How...
2
by: dschectman | last post by:
This appears to be a feature of IE JavaScript. I am running IE 6.0 with the latest patches from Microsoft. Are there any workarounds other than re-coding the source HTML to place all the...
13
by: vd12005 | last post by:
Hello, i would like to sort(ed) and reverse(d) the result of many huge dictionaries (a single dictionary will contain ~ 150000 entries). Keys are words, values are count (integer). i'm...
1
by: ++imanshu | last post by:
Hi, Is there a reason why two similarly named functions Sorted and Reversed return different types of data or is it an accident. Thanks, ++imanshu
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
0
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: Vimpel783 | last post by:
Hello! Guys, I found this code on the Internet, but I need to modify it a little. It works well, the problem is this: Data is sent from only one cell, in this case B5, but it is necessary that data...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
1
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
1
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
1
by: Shællîpôpï 09 | last post by:
If u are using a keypad phone, how do u turn on JavaScript, to access features like WhatsApp, Facebook, Instagram....
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.