Advertisement
Guest User

Untitled

a guest
Nov 21st, 2019
96
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 3.45 KB | None | 0 0
  1. class BinHeap:
  2.     def __init__(self, nondecreasing=True):
  3.         self.heapList = [0]
  4.         self.current_size = 0
  5.         nondecreasing = True
  6.  
  7.     def build_heap(self, alist):
  8.         i = len(alist) // 2
  9.         self.current_size = len(alist)
  10.         self.heapList = [0] + alist[:]
  11.         print(len(self.heapList), i)
  12.  
  13.         while i > 0:
  14.             print(self.heapList, i)
  15.             self.perc_down(i)
  16.             i = i - 1
  17.  
  18.         print(self.heapList, i)
  19.  
  20.     def perc_down(self, i):
  21.         while (i * 2) <= self.current_size:
  22.             mc = self.min_child(i)
  23.  
  24.             if self.heapList[i] > self.heapList[mc]:
  25.                 self.heapList[i], self.heapList[mc] = self.heapList[mc], self.heapList[i]
  26.  
  27.             i = mc
  28.  
  29.     def min_child(self, i):
  30.         if i * 2 + 1 > self.current_size:
  31.             return i * 2
  32.         else:
  33.             if self.heapList[i * 2] < self.heapList[i * 2 + 1]:
  34.                 return i * 2
  35.             else:
  36.                 return i * 2 + 1
  37.  
  38.     def perc_up(self, i):
  39.         while i // 2 > 0:
  40.  
  41.             if self.heapList[i] < self.heapList[i // 2]:
  42.                 self.heapList[i // 2], self.heapList[i] = self.heapList[i], self.heapList[i // 2]
  43.  
  44.             i = i // 2
  45.  
  46.     def insert(self, k):
  47.         self.heapList.append(k)
  48.         self.current_size = self.current_size + 1
  49.         self.perc_up(self.current_size)
  50.  
  51.     def del_min(self):
  52.         ret_val = self.heapList[1]
  53.         self.heapList[1] = self.heapList[self.current_size]
  54.         self.current_size = self.current_size - 1
  55.         self.heapList.pop()
  56.         self.perc_down(1)
  57.         return ret_val
  58.  
  59.     def is_empty(self):
  60.         return self.current_size == 0
  61.    
  62.     def __str__(self):
  63.         returnstring = ""
  64.         for i in range(len(self.heapList)):
  65.             returnstring += str(self.heapList[i]) + " "
  66.         return returnstring
  67.    
  68.     def __len__(self):
  69.         return len(self.heapList)
  70.    
  71.     def findMaximumElement(self, heap, n):
  72.         maximumElement = heap[0];
  73.         j = 1
  74.         for i in range(1, n):
  75.             if self.heapList[i] > self.heapList[j]:
  76.                 j = i
  77.         return j
  78.     def findMinimumElement(self, heap, n):
  79.         minimumElement = heap[0];
  80.         j = 1
  81.         for i in range(1, n):
  82.             if self.heapList[j] > self.heapList[i]:
  83.                 j = i
  84.         return j
  85.    
  86.     def sort(self, maxormin):
  87.         if(maxormin == True):
  88.             j = self.findMaximumElement(self.heapList, len(self.heapList))
  89.             i = self.heapList[1]
  90.             self.heapList[1], self.heapList[j] = self.heapList[j], self.heapList[1]
  91.             for k in range(len(self.heapList)//2):
  92.                 for i in range(1,len(self.heapList)-1):
  93.                     j = i+1
  94.                     if(self.heapList[j] < self.heapList[i])-1:
  95.                         self.heapList[i], self.heapList[j] = self.heapList[j], self.heapList[i]
  96.         elif(maxormin == False):
  97.             j = self.findMinimumElement(self.heapList, len(self.heapList))
  98.             i = self.heapList[1]
  99.             self.heapList[1], self.heapList[j] = self.heapList[j], self.heapList[1]
  100.             for k in range(len(self.heapList)//2):
  101.                 for i in range(1,len(self.heapList)-1):
  102.                     j = i+1
  103.                     if(self.heapList[j] > self.heapList[i])-1:
  104.                         self.heapList[i], self.heapList[j] = self.heapList[j], self.heapList[i]
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement