Augmented Binary Heaps

Please use python 2.7 parts of the code have been provided just do the parts that are need please provide functional working code and screenshots for good feedback thanks!

import sys import numbergenerator

class AugmentedBinaryHeap(object): def __init__(self): self.heap_array = [] pass

def insert(self, key, value): # Insert Key/Value pair pass

def removeMin(self): # Remove minimum key in the data structure pass

def printMin(self): # return the minimum key value pair in the data structure return (-1,-1) pass

def find(self, key): # finding the value associated with the given key return -1 pass

def changeKey(self, fromKey, toKey): # Changes the key of a pair in the data structure pass

def printHeap(self): # returns the array of the internal heap return self.heap_array

n,s,m=[int(x) for x in sys.stdin.readline().split()] ng = numbergenerator.NumberGenerator(s, m) ds = AugmentedBinaryHeap() for i in xrange(n): line = sys.stdin.readline().split() if line[0] == "Insert": rep = int(line[1]) for j in xrange(rep): key = ng.GetNumber() value = ng.GetNumber() ds.insert(key, value) elif line[0] == "RemoveMin": rep = int(line[1]) for j in xrange(rep): ds.removeMin() elif line[0] == "PrintMin": print ' '.join(str(x) for x in ds.printMin()) elif line[0] == "Find": key = int(line[1]) print ds.find(key) elif line[0] == "ChangeKey": fromKey = int(line[1]) toKey = int(line[2]) ds.changeKey(int(line[1]), int(line[2])) elif line[0] == "PrintHeap": heapArray = ds.printHeap() print ' '.join(str(x[0])+" "+str(x[1]) for x in heapArray)

Number Genorator code

import random

class NumberGenerator(object): def __init__(self, seed, maxNumber): self.seed = seed self.maxNumber = maxNumber random.seed(seed)

def GetNumber(self): return random.randint(1,self.maxNumber)

[Please use Python 2.7 for this assignment, otherwise, the number generator won't produce the same numbers as the grading script] In this problem your job is to design and implement a data structure to store information in the form of key/value pairs, that offers the following operation at the given running time. You can find more information on designing this data structure in hw6 handout (it has been updated) Insert (key, value): For a given key/value pair, adds it to the data structure. Should run in O(log(n)) RemoveMin0: Removes the smallest key in the data structure and the value associated with it. Should run in O(log(n)) PrintMin(): Prints the smallest key in the data structure and the value associated with it. Should run in O(1) Find(key): Looks up the given key in the data structure, and prints the value associated with it. Prints -1 ifthe key is not present. Should run in O(1 Change Key(FromKey, Tokey): Looks up the pair containing From Key, and changes its key to ToKey, so that from now on, its associated value can be looked up ith the new key, not the old one. Should run in O(log(n)). This operation doesn't do anything if FromKey IS NOT present or ToKey IS present in the data structure already PrintHeap(): Prints the contents of the internal heap, in the order they are stored in the array Note that all the keys and values are greater than 0 In addition, you are provided with a number generator that produces numbers (from 1 to max value) that you will use as keys and value to store in the data structure according to input commands as follows Insert n: Where n is a number from 1 to 10n6. For this command, you should get n keys and values from the number generator, and store them in the data structure Note that you should use the first generated number as the first key, second generated number as the firstvalue, third generated number as the second key, and so on n addition, inserting (k, v) where key k is already present in the data structure, simply updated its associated value to v RemoveMin n: Where n is a number from 1 to 10 6. For this command, you should remove the minimum key (and its associated value) from the data structure n times If the the data structure has fewer than or equal to n pairs stored in it, it will be emptied as a result of this command PrintMin: For this command, you should print the minimum key in the data structure and its associated value separated by one space in a line. You will never see this hen the data structure in empty Find k: where k is an integer greater than 0. For this command, you should bring the value associated with key k in the data structure, or print -1 if k is not present. Change Key k1 k2: where k1 and k2 are integers greater than 0. For this command, if key k1 is present and key k2 is not, you should change k1 to k2 (associate value of k to k2 and remove k1). Otherwise, this command is ignored PrintHeap: For this command, you should print the content of the internal heap, in the order they appear in the array, separated by space, all in one line, in the form k1 1 k2 v2 k3 v3 and so on Input Specification: In the first line of input comes three space separated integers n, s, m, where n is the number of commands that follows, s is the seed to the number generator and m is the maximum value that should be generated by the generator. Use s and m to initialize the number generator Each of the n following lines contains a single command [Please use Python 2.7 for this assignment, otherwise, the number generator won't produce the same numbers as the grading script] In this problem your job is to design and implement a data structure to store information in the form of key/value pairs, that offers the following operation at the given running time. You can find more information on designing this data structure in hw6 handout (it has been updated) Insert (key, value): For a given key/value pair, adds it to the data structure. Should run in O(log(n)) RemoveMin0: Removes the smallest key in the data structure and the value associated with it. Should run in O(log(n)) PrintMin(): Prints the smallest key in the data structure and the value associated with it. Should run in O(1) Find(key): Looks up the given key in the data structure, and prints the value associated with it. Prints -1 ifthe key is not present. Should run in O(1 Change Key(FromKey, Tokey): Looks up the pair containing From Key, and changes its key to ToKey, so that from now on, its associated value can be looked up ith the new key, not the old one. Should run in O(log(n)). This operation doesn't do anything if FromKey IS NOT present or ToKey IS present in the data structure already PrintHeap(): Prints the contents of the internal heap, in the order they are stored in the array Note that all the keys and values are greater than 0 In addition, you are provided with a number generator that produces numbers (from 1 to max value) that you will use as keys and value to store in the data structure according to input commands as follows Insert n: Where n is a number from 1 to 10n6. For this command, you should get n keys and values from the number generator, and store them in the data structure Note that you should use the first generated number as the first key, second generated number as the firstvalue, third generated number as the second key, and so on n addition, inserting (k, v) where key k is already present in the data structure, simply updated its associated value to v RemoveMin n: Where n is a number from 1 to 10 6. For this command, you should remove the minimum key (and its associated value) from the data structure n times If the the data structure has fewer than or equal to n pairs stored in it, it will be emptied as a result of this command PrintMin: For this command, you should print the minimum key in the data structure and its associated value separated by one space in a line. You will never see this hen the data structure in empty Find k: where k is an integer greater than 0. For this command, you should bring the value associated with key k in the data structure, or print -1 if k is not present. Change Key k1 k2: where k1 and k2 are integers greater than 0. For this command, if key k1 is present and key k2 is not, you should change k1 to k2 (associate value of k to k2 and remove k1). Otherwise, this command is ignored PrintHeap: For this command, you should print the content of the internal heap, in the order they appear in the array, separated by space, all in one line, in the form k1 1 k2 v2 k3 v3 and so on Input Specification: In the first line of input comes three space separated integers n, s, m, where n is the number of commands that follows, s is the seed to the number generator and m is the maximum value that should be generated by the generator. Use s and m to initialize the number generator Each of the n following lines contains a single command