# 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

```