本文共 1738 字，大约阅读时间需要 5 分钟。

最大堆

class Array(object):    def __init__(self,size=32):        self._size = size        self._items = [None] * size        def __getitem__(self,index):        return self._items[index]    def __setitem(self,index,value):        self._items[index] = value        def __len__(self):        return self._size    def clear(self,value=None):        for _ in range(self._items):            self._items[_] = value        def iter(self):        for _ in self._items:            yield _    class MaxHeap(Array):	def __init__(self,maxsize=None):		self.maxsize = maxsize		self._elements = Array(maxsize)		self._count = 0		def __len__(self):		return self._count	def add(self,value):		if self._count >= self.maxsize:			raise Exception('Full of size')		 self._elements[self._count] = value		 self._count += 1		 self._siftup(self._count-1)	def _siftup(self,idx):		'''		用递归的方法满足最大堆的特性		'''		if idx > 0:			parent = (idx-1) // 2			if self._elements[idx] > self._elements[parent]:				self._elements[idx],self._elements[parent] = self._elements[parent],self._elements[idx]				self._siftup(parent)	def extract(self):		if self._count <= 0:			raise Exception("Empty!!")		value = self._elements[0]		self.clear -= 1		self._elements[0] = self._elements[self._count]		self._siftdown(0)		return value		def _siftdown(self,idx):		left = 2 * idx + 1		right = 2 * idx + 2		largest = idx				if (left < self._count and self._elements[left] >= self._elements[largest] and self._elements[left] > self._elements[right]):			largest = left		elif right < self._count and self._elements[right] >= self._elements[largest]:			largest = right				if largest != idx:			self._elements[largest],self._elements[idx] = self._elements[idx],self._elements[largest]			self._siftdown(largest)

转载地址：http://theyz.baihongyu.com/