Advertisement
Guest User

Untitled

a guest
Apr 23rd, 2019
75
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 3.17 KB | None | 0 0
  1. import datetime
  2. import time
  3. import random
  4. import string
  5. import array as arr
  6.  
  7. class Task(object):
  8. def __init__(self, name,priority,time):
  9. self.name = name
  10. self.priority = priority
  11. self.time = time
  12.  
  13. class MaxHeap:
  14. def __init__(self, items=[]): # initiate the heap
  15. super().__init__()
  16. self.heap = [0]
  17. for i in items: # O(n) loop on all items ( n is number of items)
  18. self.heap.append(i)
  19. self.__floatUp(len(self.heap) - 1)
  20.  
  21. def push(self, data): # push new value to the heap, and sort it
  22. self.heap.append(data)
  23. self.__floatUp(len(self.heap) - 1) # according to floatUp
  24.  
  25. def peek(self): # reveals the maximum value of the heap # O(1)
  26. if self.heap[1]:
  27. return self.heap[1]
  28. else:
  29. return False
  30.  
  31. def pop(self): # removes the maximum value of the heap # O()
  32. if len(self.heap) > 2:
  33. self.__swap(1, len(self.heap) - 1)
  34. max = self.heap.pop()
  35. self.__bubbleDown(1) # like bubbleDown
  36. elif len(self.heap) == 2:
  37. max = self.heap.pop()
  38. else:
  39. max = False
  40. return max
  41.  
  42. def __swap(self, i, j): # swaps locations of objects inside the heap O(1)
  43. self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
  44.  
  45. def __floatUp(self, index): # bubble up a value to its right place # O(n^2)
  46. parent = index//2
  47. if index <= 1:
  48. return
  49. elif self.heap[index].priority > self.heap[parent].priority:
  50. self.__swap(index, parent)
  51. self.__floatUp(parent)
  52.  
  53. def __bubbleDown(self, index): # bubble down a value to its right place
  54. left = index * 2
  55. right = index * 2 + 1
  56. largest = index
  57. if len(self.heap) > left and self.heap[largest].priority < self.heap[left].priority:
  58. largest = left
  59. if len(self.heap) > right and self.heap[largest].priority < self.heap[right].priority:
  60. largest = right
  61. if largest != index:
  62. self.__swap(index, largest)
  63. self.__bubbleDown(largest)
  64.  
  65. def heapLen(self): # shows heap length
  66. return len(self.heap) - 1
  67.  
  68.  
  69. print("_-_-_-_- START -_-_-_-_")
  70. print("Data Structure - Maman 14")
  71. print("Barak Kaminski #20106761\n")
  72.  
  73.  
  74. m = MaxHeap([])
  75. Arr = []
  76. runtime = 0
  77. ind = 1
  78.  
  79. print("Insert the amount of Jobs to run:")
  80. n = int(input())
  81. print("\nPlease type Name, Priority and Time for the job(s):\n for example: A 7 12")
  82. for i in range(0, n):
  83. lst = list(map(str, input().split()))
  84. m.push(Task(lst[0],lst[1],lst[2]))
  85.  
  86. print("\n\nJobs ran as follow:")
  87. ind = 1
  88. while m.heapLen() > 0: # continues while the heap is not empty
  89.  
  90. i = m.peek()
  91. print (ind,i.name,i.priority,i.time,runtime)
  92. runtime = runtime + int(i.time)
  93. ind = ind + 1
  94. m.pop()
  95.  
  96. New_Job = random.randint(1, 100) # adds random aspect
  97. chances = 60
  98. if New_Job > chances: ##For example 20%
  99. ranName = random.choice(string.ascii_letters)
  100. ranPriority = str(random.randint(1, 10))
  101. ranTime = str(random.randint(1, 50))
  102. i = Task(ranName,ranPriority,ranTime)
  103. m.push(i) # pushes randomized value into the heap
  104. print("*added Job with values: -> ", i.name,i.priority,i.time) # tells new job is added
  105.  
  106.  
  107. print("\n\nAll JOBS DONE in total runtime of", runtime, "time units")
  108.  
  109.  
  110. print("\n_-_-_-_- End -_-_-_-_")
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement