classminheap(object):
"""implements a minimal heap without a size restriction"""def__init__(self):
"""create a variable-size empty minheap"""self.__h = list()
def__str__(self):
"""return a string representation of the minheap"""returnstr(self.__h)
def__len__(self):
"""return the size of the minheap"""returnlen(self.__h)
defis_empty(self):
"""return if the collection is empty or not"""returnlen(self)==0def__left(self,i):
"""return the index of the left children of i"""return1+(i<<1) def __right(self,i): """return the index of the right children of i""" return (1+i)<<1 def __parent(self,i): """return the index of the parent of i""" assert i>0return (i-1)>>1defget_min(self):
"""return the minimum element of the heap"""assertlen(self)!=0returnself.__h[0]
def__heapify_up(self,i):
"""moves the element up in the tree assuming that the rest of the tree satisfies the heap property """asserti>=0ifi!=0:
ip = self.__parent(i)
ifself.__h[ip]>self.__h[i]:
self.__h[ip],self.__h[i] = self.__h[i],self.__h[ip]
self.__heapify_up(ip)
def__heapify_down(self,i):
"""moves the element down in the tree assuming that the rest of the tree satisfies the heap property """il,ir,ib = self.__left(i),self.__right(i),iifil<len(self) and self.__h[i]>self.__h[il]: ib = ilifir<len(self) and self.__h[ib]>self.__h[ir]: ib = irifib!=i:self.__h[i],self.__h[ib] = self.__h[ib],self.__h[i]
self.__heapify_down(ib)
definsert(self,x):
"""insert x in the minheap"""self.__h.append(x)
iflen(self)>1:
self.__heapify_up(len(self)-1)
defremove_min(self):
"""remove the minimum from the heap"""assertlen(self)!=0self.__h[0] = self.__h[-1]
self.__h.pop()
iflen(self)>1:
self.__heapify_down(0)
Comments (0)
HTTPSSSH
You can clone a snippet to your computer for local editing.
Learn more.