[Tutor] Case study: writing an Python extension type in C [C extensions / priority queues / PyHeap]

[Danny Yoo]

[note: you may want to skip this message if you haven't programmed in C]


Hi everyone,

I got off my lazy behind and typed up a preliminary example of an C
extension.  I've chosen to do an implementation of a "priority queue"
using the "heap" data structure.


A "priority queue" is something that keeps track of items and their
priorities, and makes it relatively fast to grab the most "important"
element at any given time.  A simple way of implementing this in Python
would be to use a sorted list:

###
class PriorityQueue:
    """This is a simple implementation of a priority queue."""

    def __init__(self, cmp=cmp):
        self.cmp = cmp
        self.items = []

    def push(self, obj):
        self.items.append(obj)
        self.items.sort(cmp)

    def pop(self):
        return self.items.pop()
###


No sweat.  *grin* And this works well enough:

###
>>> pq = PriorityQueue()
>>> pq.push( (1, "eat") )
>>> pq.push( (2, "sleep") )
>>> pq.push( (3, "have life") )
>>> pq.pop()
(3, 'have life')
>>> pq.push( (42, "program") )
>>> pq.pop()
(42, 'program')
>>> pq.pop()
(2, 'sleep')
>>> pq.pop()
(1, 'eat')
>>> pq.pop()
Traceback (most recent call last):
  File "<stdin>", line 1, in ?
  File "/tmp/python-539-9L", line 13, in pop
IndexError: pop from empty list
###

The only problem here is that inserting into this priority queue costs
quite a bit: it requires us to resort the list whenever we add a new task
to the list.  Heaps are a data structure that allow us to do insertions
and max-grabbing at a fairly low cost.


I've written the code to do this with heaps.  I'll start writing an HTML
page to present this stuff more leisurely, and perhaps this will interest
people who want to see how Python extensions work.

And now an apology: I lost the email of the people who contacted me about
writing this tutorial!  please forgive me for not responding!  For people
who haven't been insulted by my unresponsiveness, the code can be found
here:

    http://hkn.eecs.berkeley.edu/~dyoo/python/pyheap/PyHeap-0.1.tar.gz

Any suggestions would be greatly appreciated.  I promise I won't ignore
the emails this time.  *grin*



Hope this helps!