+ """implements a minheap"""
+ def __init__(self,cap=100):
+ """creates an empty minheap with the given capacity"""
+ self.__h = [ None for i in range(cap) ]
+ """return the string representation of the minheap"""
+ return str(self.__h[:self.__len])
+ """return the number of elements in the collection"""
+ """return the capacity of the minheap"""
+ """return if the collection is empty or not"""
+ """return if the collection is full or not"""
+ return len(self)==len(self.__h)
+ """return the index of the parent of the given index"""
+ """return the index of the left child of the given index"""
+ """return the index of the right child of the given index"""
+ def __heapify_up(self,i):
+ """moves the element up in the tree assuming that the rest of the tree
+ satisfies the heap property
+ if self.__h[p]>self.__h[i]:
+ self.__h[p],self.__h[i] = self.__h[i],self.__h[p]
+ def __heapify_down(self,i):
+ """moves the element down in the tree assuming that the rest of the
+ tree satisfies the heap property
+ l,r,b = self.__left(i),self.__right(i),i
+ if l<len(self) and self.__h[l]<self.__h[b]: b = l
+ if r<len(self) and self.__h[r]<self.__h[b]: b = r
+ self.__h[b],self.__h[i] = self.__h[i],self.__h[b]
+ """return the minimum of the collection"""
+ """remove the minimum of the collection"""
+ self.__h[0] = self.__h[len(self)-1] ; self.__len -= 1
+ """insert the element in the collection"""
+ assert len(self)!=self.capacity()
+ self.__h[len(self)] = x; self.__len += 1
+ self.__heapify_up(self.__len-1)
