HEAP/priority queue

[François Pinard]

Courageous <jkraska1 at san.rr.com> writes:

> Is there a heap anywhere in the python modules? I did an exaustive grep
> on all the html files, and could find nothing. I'd prefer a native module,
> of course.

I once discussed exactly this with Guido, who replied he did not feel like
natively supporting every kind of interesting data structures.  I thought
I did one such module (in Python), but do not find it...

OK, I just wrote this in a rush for you.  Not tested yet.  Maybe tomorrow?
If you test it before I do, tell me where my bugs were!  Keep happy! :-)


"""\
Handle heaps (where a[k] <= a[2*k+1] && a[k] <= a[2*k+2]).

Heaps are arrays for which a[k] <= a[2*k+1] and a[k] <= a[2*k+2]
simultaneously, for all k, counting elements from 0.  For the sake of
comparison, unexisting elements are considered to be infinite.  The
interesting property of a heap is that a[0] is its smallest element.
"""

class Heap:

    def __init__(self, compare):
        self.compare = compare
        self.array = []

    def resift(self):
        array = self.array
        compare = self.compare
        low, high = 0, 1
        while high < len(array):
            if high+1 < len(array) and compare(array[high], array[high+1]) > 0:
                high = high+1
            if compare(array[low], array[high]) <= 0:
                break
            array[low], array[high] = array[high], array[low]
            low, high = high, 2*low+1

    def increase(self, item):
        array = self.array
        compare = self.compare
        array.append(item)
        high = len(array) - 1
        while high > 0:
            low = (high-1)/2
            if compare(array[low], array[high]) <= 0:
                break
            array[low], array[high] = array[high], array[low]
            high = low

    def decrease(self):
        array = self.array
        array[0] = array.pop()
        self.resift()

-- 
François Pinard   http://www.iro.umontreal.ca/~pinard