File size: 2,308 Bytes
40521b8 | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 | class BinaryHeap:
def __init__(self):
self.heap=[]
self.dataLoopUp={}
def parent(self,i):
return int((i-1)/2)
def left(self,i):
return i*2+1
def right(self,i):
return i*2+2
def empty(self):
if len(self.heap)==0:
return True
else:
return False
def processUp(self,i=-1):
if i==(-1):
i=len(self.heap)-1
while i>0 and self.heap[self.parent(i)][0]>self.heap[i][0]:
self.heap[self.parent(i)],self.heap[i]=self.heap[i],self.heap[self.parent(i)]
self.dataLoopUp[self.heap[self.parent(i)][1]]=self.parent(i)
self.dataLoopUp[self.heap[i][1]]=i
i=self.parent(i)
def processDown(self,i=-1):
if i==(-1):
i=0
while (self.left(i)<len(self.heap) and self.heap[self.left(i)]<self.heap[i]) or (self.right(i)<len(self.heap) and self.heap[self.right(i)]<self.heap[i]):
if self.left(i)<len(self.heap) and self.heap[self.left(i)]<self.heap[i]:
j=self.left(i)
else:
j=self.right(i)
self.heap[i],self.heap[j]=self.heap[j],self.heap[i]
self.dataLoopUp[self.heap[i][1]]=i
self.dataLoopUp[self.heap[j][1]]=j
i=j
def insert(self,ele):
"""if ele[1] in self.dataLoopUp:
decrease"""
self.heap.append(ele)
self.dataLoopUp[ele[1]]=len(self.heap)-1
#i=len(self.heap)-1
self.processUp()
def extractMin(self):
minimum=self.heap[0]
self.heap[0]=self.heap[-1]
self.dataLoopUp[self.heap[0][1]]=0
del self.heap[-1]
del self.dataLoopUp[minimum[1]]
self.processDown()
return minimum[1]
def decreaseKey(self,data,f):
if f>self.heap[self.dataLoopUp[data]][0]:
return
my_list=list(self.heap[self.dataLoopUp[data]])
my_list[0]=f
self.heap[self.dataLoopUp[data]]=tuple(my_list)
self.processUp(self.dataLoopUp[data]) |