Pure python implicit min-heap implementation that subclasses list. Includes efficient build-heap initialiser. Insert/Delete operations with pop() and append() methods.

minheap.py

#!/usr/bin/python

class Heap(list):
	def sift_up(self, idx):
		v = self[idx]
		if self.root() == idx:
			return
		pidx = self.parent(idx)
		pv = self[pidx]
		if pv < v:
			return

		self[pidx] = v
		self[idx] = pv
		self.sift_up(pidx)

	def sift_down(self, idx):
		v = self[idx]
		#print 'sift down', idx, '->', v
		lidx = self.left(idx)
		ridx = self.right(idx)
		kids = []
		try:
			kids.append((self[lidx], lidx))
			kids.append((self[ridx], ridx))
		except IndexError:
			pass
		if not len(kids):
			return
		kids.sort()
		(cval, cidx) = kids[0]
		if not v < cval:
			self[idx] = cval
			self[cidx] = v
			self.sift_down(cidx)
			return

	def __init__(self, sz):
		from math import floor, ceil, log
		super(Heap,self).__init__([x for x in xrange(sz + 1, 0, -1)])
		lf = int(floor(log(sz, 2)))
		if lf < 0:
			return
		f = (1 << lf) - 1
		c = (1 << lf)
		for x in xrange(f, sz):
			self.sift_up(x + 1)

		c = (c - (sz - f)) / 2
		for x in xrange(self.parent(sz), self.parent(sz) + c):
			self.sift_up(x + 1)

	def parent(self, idx):
		return idx / 2
	def left(self, idx):
		return idx * 2
	def right(self, idx):
		return idx * 2 + 1
	def root(self):
		return 1

	def __getitem__(self, idx):
		assert(idx != 0)
		return super(Heap,self).__getitem__(idx)
	def __str__(self):
		return str(self[1:])
	def __repr__(self):
		return str(self[1:])
	def __iter__(self):
		return iter(self[1:])
	def __len__(self):
		return super(Heap,self).__len__() - 1

	def pop(self):
		ret = self[1]
		new_root = super(Heap,self).pop()
		if len(self):
			self[1] = new_root
			self.sift_down(self.root())
		return ret

	def append(self, val):
		super(Heap,self).append(val)
		self.sift_up(len(self))

if __name__ == '__main__':
	from sys import argv
	x = Heap(int(argv[1]))
	print len(x), x
	print
	while len(x):
		print x.pop(), x

	print
	x.append(100)
	print x
	x.append(200)
	print x
	x.append(300)
	print x

	print
	while len(x):
		print x.pop(), x