Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import datetime
- import time
- import random
- import string
- import array as arr
- class Task(object):
- def __init__(self, name,priority,time):
- self.name = name
- self.priority = priority
- self.time = time
- class MaxHeap:
- def __init__(self, items=[]): # initiate the heap
- super().__init__()
- self.heap = [0]
- for i in items: # O(n) loop on all items ( n is number of items)
- self.heap.append(i)
- self.__floatUp(len(self.heap) - 1)
- def push(self, data): # push new value to the heap, and sort it
- self.heap.append(data)
- self.__floatUp(len(self.heap) - 1) # according to floatUp
- def peek(self): # reveals the maximum value of the heap # O(1)
- if self.heap[1]:
- return self.heap[1]
- else:
- return False
- def pop(self): # removes the maximum value of the heap # O()
- if len(self.heap) > 2:
- self.__swap(1, len(self.heap) - 1)
- max = self.heap.pop()
- self.__bubbleDown(1) # like bubbleDown
- elif len(self.heap) == 2:
- max = self.heap.pop()
- else:
- max = False
- return max
- def __swap(self, i, j): # swaps locations of objects inside the heap O(1)
- self.heap[i], self.heap[j] = self.heap[j], self.heap[i]
- def __floatUp(self, index): # bubble up a value to its right place # O(n^2)
- parent = index//2
- if index <= 1:
- return
- elif self.heap[index].priority > self.heap[parent].priority:
- self.__swap(index, parent)
- self.__floatUp(parent)
- def __bubbleDown(self, index): # bubble down a value to its right place
- left = index * 2
- right = index * 2 + 1
- largest = index
- if len(self.heap) > left and self.heap[largest].priority < self.heap[left].priority:
- largest = left
- if len(self.heap) > right and self.heap[largest].priority < self.heap[right].priority:
- largest = right
- if largest != index:
- self.__swap(index, largest)
- self.__bubbleDown(largest)
- def heapLen(self): # shows heap length
- return len(self.heap) - 1
- print("_-_-_-_- START -_-_-_-_")
- print("Data Structure - Maman 14")
- print("Barak Kaminski #20106761\n")
- m = MaxHeap([])
- Arr = []
- runtime = 0
- ind = 1
- print("Insert the amount of Jobs to run:")
- n = int(input())
- print("\nPlease type Name, Priority and Time for the job(s):\n for example: A 7 12")
- for i in range(0, n):
- lst = list(map(str, input().split()))
- m.push(Task(lst[0],lst[1],lst[2]))
- print("\n\nJobs ran as follow:")
- ind = 1
- while m.heapLen() > 0: # continues while the heap is not empty
- i = m.peek()
- print (ind,i.name,i.priority,i.time,runtime)
- runtime = runtime + int(i.time)
- ind = ind + 1
- m.pop()
- New_Job = random.randint(1, 100) # adds random aspect
- chances = 60
- if New_Job > chances: ##For example 20%
- ranName = random.choice(string.ascii_letters)
- ranPriority = str(random.randint(1, 10))
- ranTime = str(random.randint(1, 50))
- i = Task(ranName,ranPriority,ranTime)
- m.push(i) # pushes randomized value into the heap
- print("*added Job with values: -> ", i.name,i.priority,i.time) # tells new job is added
- print("\n\nAll JOBS DONE in total runtime of", runtime, "time units")
- print("\n_-_-_-_- End -_-_-_-_")
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement