tsounakis

Algorithms #3 ver.2 - better

May 20th, 2022 (edited)
265
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import random
  2. import sys
  3.  
  4.  
  5. class Heap():
  6.  
  7.     def __init__(self, array):
  8.         self.array = []  # tuple (key, value)
  9.         self.pos = {}  # position of key in array
  10.         self.size = len(array)  # number of elements in min heap
  11.         for i, item in enumerate(array):
  12.             self.array.append((item[0], item[1]))
  13.             self.pos[item[0]] = i
  14.         for i in range(self.size // 2, -1, -1):
  15.             self.heapify(i)
  16.  
  17.         # display items of heap
  18.     def display(self):
  19.         print('Min array =', end=' ')
  20.         for i in range(self.size):
  21.             print(f'({self.array[i][0]} : {self.array[i][1]})', end=' ')
  22.         print()
  23.     # is heap empty ?
  24.  
  25.     def isEmpty(self):
  26.         return self.size == 0
  27.     # i is an array index
  28.     # modify array so that i roots a heap, down-heap
  29.  
  30.     def heapify(self, i):
  31.         smallest = i
  32.         le = 2 * i + 1
  33.         ri = 2 * i + 2
  34.         if le < self.size and self.array[le][1] < self.array[smallest][1]:
  35.             smallest = le
  36.         if ri < self.size and self.array[ri][1] < self.array[smallest][1]:
  37.             smallest = ri
  38.         if smallest != i:
  39.             # update pos
  40.             self.pos[self.array[smallest][0]] = i
  41.             self.pos[self.array[i][0]] = smallest
  42.             # swap
  43.             self.array[smallest], self.array[i] = self.array[i], self.array[smallest]
  44.             self.heapify(smallest)
  45.  
  46.     # return the min element of the heap
  47.     def getMin(self):
  48.         if self.size == 0:
  49.             return None
  50.         return self.array[0]
  51.  
  52.     # return and remove the min element of the heap
  53.     def pop(self):
  54.         if self.size == 0:
  55.             return None
  56.         root = self.array[0]
  57.         lastNode = self.array[self.size - 1]
  58.         self.array[0] = lastNode
  59.         del self.array[self.size - 1]
  60.         # update pos
  61.         self.pos[lastNode[0]] = 0
  62.         del self.pos[root[0]]
  63.         self.size -= 1
  64.         self.heapify(0)
  65.         return root
  66.  
  67.     # item (key, value) to push
  68.     # modify array to include item
  69.     def push(self, item):
  70.         # push an item at the end with big value
  71.         if self.size < len(self.array):
  72.             self.array[self.size] = (item[0], float('inf'))
  73.         else:
  74.             self.array.append((item[0], float('inf')))
  75.         self.pos[item[0]] = self.size
  76.         self.size += 1
  77.         self.decreaseKey(item)
  78.  
  79.     # decrease value of item (key, value)
  80.     # with value smaller than current
  81.     def decreaseKey(self, item):
  82.         i = self.pos[item[0]]
  83.         val = item[1]
  84.         # new value must be smaller than current
  85.         if self.array[i][1] <= val:
  86.             return
  87.         self.array[i] = item
  88.         # check if is smaller than parent
  89.         p = (i - 1) // 2
  90.         while i > 0 and self.array[i][1] < self.array[p][1]:
  91.             # update pos
  92.             self.pos[self.array[i][0]] = p
  93.             self.pos[self.array[p][0]] = i
  94.             # swap
  95.             self.array[p], self.array[i] = self.array[i], self.array[p]
  96.             i = p
  97.             p = (i - 1) // 2
  98.  
  99.     # increase value of item (key, value),
  100.     # with value greater than current
  101.     def increaseKey(self, item):
  102.         i = self.pos[item[0]]
  103.         val = item[1]
  104.         # new value must be greater than current
  105.         if self.array[i][1] >= val:
  106.             return None
  107.         self.array[i] = item
  108.         # check children
  109.         self.heapify(i)
  110.  
  111.     # change value of item (key, value),
  112.     # decreaseKey or increaseKey, Running Time: O(log n)
  113.     def changeKey(self, item):
  114.         i = self.pos[item[0]]
  115.         val = item[1]
  116.         if val < self.array[i][1]:
  117.             self.decreaseKey(item)
  118.         if val > self.array[i][1]:
  119.             self.increaseKey(item)
  120.  
  121.     # check if exists an item with key = key
  122.     def isInHeap(self, key):
  123.         if self.pos.get(key) == None:
  124.             return False
  125.         if self.pos[key] < self.size:
  126.             return True
  127.         return False
  128.  
  129.     # get the value of item with key = key
  130.     def getValueMinHeap(self, key):
  131.         if self.pos.get(key) == None:
  132.             return None
  133.         if self.pos[key] < self.size:
  134.             return self.array[self.pos[key]][1]
  135.         return None
  136.  
  137.     # This function deletes key at index i. It first reduces
  138.     # value to minus infinite and then calls pop()
  139.     def deleteKey(self, item):
  140.         self.decreaseKey((item[0], float('-inf')))
  141.         self.pop()
  142.  
  143.  
  144. class Problem():
  145.     def __init__(self):
  146.         self.maxHeap = Heap([])
  147.         self.minHeap = Heap([])
  148.  
  149.     def addNum(self, i):
  150.         if self.maxHeap.isInHeap(i):
  151.             self.maxHeap.changeKey((i[0], i[1]))
  152.             return
  153.         elif self.minHeap.isInHeap(i):
  154.             self.minHeap.changeKey((i[0], i[1]))
  155.             return
  156.         if not self.maxHeap.array or i[1] < -self.maxHeap.array[0][1]:
  157.             self.maxHeap.push((i[0], -i[1]))
  158.         else:
  159.             self.minHeap.push(i)
  160.  
  161.     def balance(self):
  162.         if self.minHeap.size - self.maxHeap.size >= 2:
  163.             temp = self.minHeap.pop()
  164.             self.maxHeap.push((temp[0], -temp[1]))
  165.         elif self.maxHeap.size - self.minHeap.size >= 2:
  166.             temp = self.maxHeap.pop()
  167.             self.minHeap.push((temp[0], -temp[1]))
  168.  
  169.     def median(self):
  170.         # print('Max heap:\t{}\nMin heap:\t{}'.format(
  171.         #    self.maxHeap.array, self.minHeap.array))
  172.         if self.minHeap.size == self.maxHeap.size:
  173.             return ((self.minHeap.array[0][1] - self.maxHeap.array[0][1]) / 2)
  174.         elif self.minHeap.size > self.maxHeap.size:
  175.             return float(self.minHeap.array[0][1])
  176.         else:
  177.             return float(-self.maxHeap.array[0][1])
  178.  
  179.  
  180. if __name__ == '__main__':
  181.     prob = Problem()
  182.     random.seed()
  183.     for i in range(500000):
  184.         # prob.addNum(random.randint(1, 1000))
  185.         prob.addNum(((str(random.randint(0, 2000)) + ('N, ' if random.randint(0, 2) % 2 == 0 else 'S, ') +
  186.                     str(random.randint(0, 2000)) + ('E' if random.randint(0, 2) % 2 == 0 else 'W')), random.randrange(-2000, 3000)/100))
  187.         prob.balance()
  188.     print("The median temperature is {} C.".format(prob.median()))
  189.  
RAW Paste Data Copied