Please use python code and show screenshot of functional WORKING code that corre

Question

Please use python code and show screenshot of functional WORKING code that correctly answers the BINARY HEAP problem a portion of the code has been provided just work off the code there and provide the rest.

Comment areas is where code needs to be inserted

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)

Here is the code for the numbergenerator

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)

Active HW6: Problem 3: Augmented Binary Heaps Please use Python 2.7 for this assignment, otherwise, the number generator won't produce the same numbers as the grading script n 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) RemoveMin(): Removes the smallest key in the data structure and the value associated with it. Should run in O(log(n Prints the smallest key in the data structure and the value associated with it. Should run in O(1 Print Min Find(key): Looks up the given in data key the structure, and prints the value associated with it. Prints -1 if the key is not present. Should run in O(1) ChangeKey(From Key, 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 with the new key, not the old one. Should run in (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 greaterthan 0 In addition you are provided with a number generator that produces numbers (from 1 to max value) that you wi use as keys and value to store in the data structure according to input commands as follows: nsert n: here n is a number from 1 to 1 6. 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 first value, third generated number as the second key, and so on n addition nserting (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 m6. 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 when 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 1 is present and key k2 is not, you should change k1 to k2 (associate value of k to k2 and remove k 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, a n one line, in the form k1 1 k2 v2 3 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 follo 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

Explanation / Answer

class BinHeap:
def __init__(self):
self.heapList = [0]
self.currentSize = 0

def percUp(self,i):
while i // 2 > 0:
if self.heapList[i] < self.heapList[i // 2]:
tmp = self.heapList[i // 2]
self.heapList[i // 2] = self.heapList[i]
self.heapList[i] = tmp
i = i // 2

def insert(self,k):
self.heapList.append(k)
self.currentSize = self.currentSize + 1
self.percUp(self.currentSize)

def percDown(self,i):
while (i * 2) <= self.currentSize:
mc = self.minChild(i)
if self.heapList[i] > self.heapList[mc]:
tmp = self.heapList[i]
self.heapList[i] = self.heapList[mc]
self.heapList[mc] = tmp
i = mc

def minChild(self,i):
if i * 2 + 1 > self.currentSize:
return i * 2
else:
if self.heapList[i*2] < self.heapList[i*2+1]:
return i * 2
else:
return i * 2 + 1

def delMin(self):
retval = self.heapList[1]
self.heapList[1] = self.heapList[self.currentSize]
self.currentSize = self.currentSize - 1
self.heapList.pop()
self.percDown(1)
return retval

def buildHeap(self,alist):
i = len(alist) // 2
self.currentSize = len(alist)
self.heapList = [0] + alist[:]
while (i > 0):
self.percDown(i)
i = i - 1

bh = BinHeap()
bh.buildHeap([9,5,6,2,3])

print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())
print(bh.delMin())

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---