Download utils/binary_heap.py from amanr24/SafeMaps: direct link, hf CLI and curl.
- Browser
- Download file 2.31 kB
-
https://huggingface.co/spaces/amanr24/SafeMaps/resolve/main/utils/binary_heap.py
- Command line
-
hf download hf://spaces/amanr24/SafeMaps/utils/binary_heap.py
-
curl -L -o binary_heap.py https://huggingface.co/spaces/amanr24/SafeMaps/resolve/main/utils/binary_heap.py
2.31 kB
| 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]) |