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])