HEAP/priority queue
François Pinard
pinard at iro.umontreal.ca
Sat May 13 05:55:07 CEST 2000
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
More information about the Python-list
mailing list