(<-Home)
# Examples on 'How to use' are included at bottom of this page.
# For detailed explanation of code logic with example, visit
# respective function from Home page.
class heapq:
def __init__(self,heap=[]):
""" Default implementation is of minHeap.
If external list is passed as parameter it will be converted
to heap inplace. Otherwise, a new list will be returned as heap
"""
self.__heap=heap
def __siftdown(self,start,end):
"""correct a heap by placing element at end to its correct place.
It compare childs with their parent and makes parent smallest
by swapping. Same keeps looping until finds correct relation.
"""
heap=self.__heap
newitem=heap[end]
while end>start:
parentpos=(end-1)>>1
parent=heap[parentpos]
if newitem<parent:
heap[end]=parent
end=parentpos
continue
break
heap[end]=newitem
def __siftup(self,pos):
"""adjust item at pos to its correct position
and following sub tree, if misplaced"""
heap=self.__heap
child=2*pos+1
smallest=pos
if child<len(heap) and heap[smallest]>heap[child]:
smallest=child
if child+1<len(heap) and heap[smallest]>heap[child+1]:
smallest=child+1
if smallest!=pos:
# if true means that node is incorrect.
# So it swap with smaller child and recurse on child.
heap[smallest],heap[pos]=heap[pos],heap[smallest]
self.__siftup(smallest)
def heappush(self,item):
"""push item on the heap maintaining heap property.
Simply append item and then correct heap by
__siftdown
"""
heap=self.__heap
heap.append(item)
self.__siftdown(0,len(heap)-1)
def heappop(self):
"""remove item from the heap maintaining heap property.
It will swap last item with topmost and then correct
the heap by __siftup
"""
heap=self.__heap
lastitem=heap.pop()
if heap:
topmost=heap[0]
heap[0]=lastitem
self.__siftup(0)
return topmost
return lastitem
def heapify(self):
"""create heap from rawlist"""
heap=self.__heap
for i in reversed(range(len(heap)//2)):
self.__siftup(i)
def heappushpop(self,item):
"""equivalent to heappush followed by heappop but more efficient"""
heap=self.__heap
if heap and heap[0]<item:
item,heap[0]=heap[0],item
self.__siftup(0)
return item
def heapreplace(self,item):
"""equivalent to heappop followed by heappush but more efficient"""
heap=self.__heap
item,heap[0]=heap[0],item
self.__siftup(0)
return item
def __siftdown_max(self,start,end):
"""correct a heap by placing element at end to its correct place"""
heap=self.__heap
newitem=heap[end]
while end>start:
parentpos=(end-1)>>1
parent=heap[parentpos]
if newitem>parent:
heap[end]=parent
end=parentpos
continue
break
heap[end]=newitem
def __siftup_max(self,pos):
"""adjust item at pos to its correct position
and following sub tree, if misplaced"""
heap=self.__heap
child=2*pos+1
largest=pos
if child<len(heap) and heap[largest]<heap[child]:
largest=child
if child+1<len(heap) and heap[largest]<heap[child+1]:
largest=child+1
if largest!=pos:
heap[largest],heap[pos]=heap[pos],heap[largest]
self.__siftup_max(largest)
def _heappush_max(self,item):
"""push item on the heap maintaining heap property"""
heap=self.__heap
heap.append(item)
self.__siftdown_max(0,len(heap)-1)
def _heappop_max(self):
"""remove item on the heap maintaining heap property"""
heap=self.__heap
lastitem=heap.pop()
if heap:
topmost=heap[0]
heap[0]=lastitem
self.__siftup_max(0)
return topmost
return lastitem
def _heapify_max(self):
"""creates a heap from rawlist"""
heap=self.__heap
for i in reversed(range(len(heap)//2)):
self.__siftup_max(i)
def _heappushpop_max(self,item):
"""equivalent to heappush followed by heappop but more efficient"""
heap=self.__heap
if heap and heap[0]>item:
item,heap[0]=heap[0],item
self.__siftup_max(0)
return item
def _heapreplace_max(self,item):
"""equivalent to heappop followed by heappush but more efficient"""
heap=self.__heap
item,heap[0]=heap[0],item
self.__siftup_max(0)
return item
@staticmethod
def merge(iterables,*,key=None, reverse=False):
"""iterable is collection of iterable items packed in a list/tuple/set.
'merge' will merge all iterables items into one object and return it
as a generator. Key and reverse are optional parameters for user-defined
comparision of items and descending order of final objectm, respectively"""
heap=[]
tempheap=heapq(heap)
heap_append=heap.append
if reverse:
_heappop=tempheap._heappop_max
_heapify=tempheap._heapify_max
_heapreplace=tempheap._heapreplace_max
direction=-1
else:
_heappop=tempheap.heappop
_heapify=tempheap.heapify
_heapreplace=tempheap.heapreplace
direction=1
if key is None:
for order,it in enumerate(map(iter, iterables)):
try:
next=it.__next__
heap_append([next(),order*direction,next])
except StopIteration:
pass
_heapify()
while len(heap)>1:
try:
while True:
value,order,next=temp=heap[0]
yield value
temp[0]=next()
_heapreplace(temp)
except StopIteration:
_heappop()
if len(heap)==1:
value,order,next=heap[0]
yield value
yield from next.__self__
return
for order,it in enumerate(map(iter, iterables)):
try:
next=it.__next__
value=next()
heap_append([key(value),order*direction,value,next])
except StopIteration:
pass
_heapify()
while len(heap)>1:
try:
while True:
k,order,value,next=temp=heap[0]
yield value
value=next()
temp[0]=key(value)
temp[2]=value
_heapreplace(temp)
except StopIteration:
_heappop()
if len(heap)==1:
k,o,value,next=heap[0]
yield value
yield from next.__self__
@staticmethod
def nsmallest(n,iterable,key=None):
"""return n smallest element from iterable
equivalent to sorted(iterable)[:n]
"""
if n>=len(iterable):
return sorted(iterable,key=key)[:n]
if n==1:
return [min(iterable,key=key) if key else min(iterable)]
heap=[]
tempheap=heapq(heap)
heap_append=heap.append
_heapify=tempheap._heapify_max
_heapreplace=tempheap._heapreplace_max
it=iter(iterable)
if key is None:
for order,value in zip(range(n), it):
heap_append([value,order])
_heapify()
topvalue=heap[0][0]
order=n
for value in it:
if topvalue>value:
_heapreplace([value,order])
topvalue,_=heap[0]
order+=1
heap.sort()
return [value for value,order in heap]
for order,value in zip(range(n), it):
heap_append([key(value),order,value])
_heapify()
topvalue=heap[0][0]
order=n
for value in iterable[n:]:
k=key(value)
if topvalue>k:
_heapreplace([k,order,value])
topvalue,_,_=heap[0]
order+=1
heap.sort()
return [value for k,o,value in heap]
@staticmethod
def nlargest(n,iterable,key=None):
"""return n smallest element from iterable
equivalent to sorted(iterable,reverse=True)[:n]
"""
if n>=len(iterable):
return sorted(iterable,key=key,reverse=True)[:n]
if n==1: return [max(iterable,key=key) if key else max(iterable)]
heap=[]
tempheap=heapq(heap)
heap_append=heap.append
_heapify=tempheap.heapify
_heapreplace=tempheap.heapreplace
it=iter(iterable)
if key is None:
for order,value in zip(range(0,-n,-1), it):
heap_append([value,order])
_heapify()
topvalue=heap[0][0]
order=-n
for value in iterable[n:]:
if topvalue<value:
_heapreplace([value,order])
topvalue,_=heap[0]
order-=1
heap.sort(reverse=True)
return [value for value,order in heap]
for order,value in zip(range(0,-n,-1), it):
heap_append([key(value),order,value])
_heapify()
topvalue=heap[0][0]
order=-n
for value in iterable[n:]:
k=key(value)
if topvalue<k:
_heapreplace([key(value),order,value])
topvalue,_,_=heap[0]
order-=1
heap.sort(reverse=True)
return [value for k,o,value in heap]
def __repr__(self):
"""representation of heapq object on screen"""
return self.__heap.__str__()
Comments