Question

urgent

, and what is the big-O?

Write a Priority Queue method, end_of_path(path), that is given a string, path, as input, which represents the path from the root to the node of interest, and if there is a node at the end of that path, the method returns the value at that node, otherwise returns None. path is a string containing just "L"s and "R"s, representing left child and right child. So, given a priority queue represented by the list [0, 1, 2, 3, 37, 6, 5], end_of_path(LR') returns 6. The priority queue is implemented in the standard way as a python list. Copy the PriorityQueue class definition below to the beginning of your answer and add your code to the bottom of class PriorityQueue. Submit the entire class. Note: you may define additional helper methods if you wish. class PriorityQueue: def init(self): self.bin_heap self.current_size def st r__(self): str (self . bin_heap [1:]) return str(self.current_size) : def perc up(self, i ) : while i / 2 8: if self.bin_heap[i] self.bin_heap[i 21: tmp self.bin_heap [i // 2] self.bin_heap[i // 21 self.bin_heap[i] self.bin_heap [i] i i / 2 = tmp def insert (self, k) : self.bin_heap.append(k) self.current size self.current size 1 self.perc_up (self.current_size) For example: Test Result x PriorityQueue ) 1 x.insert(1) print(x.end_of_path()) x PriorityQueue () x.insert(1) x.insert(2) x.insert(3) x.insert(37) x.insert(6) x.insert(5) print(x.end_of_path (' LR')) Answer: (penalty regime: 0.10,20,30,40,50 %) 1

Answer 1

Big O is O(n) , where n is the path length , 'LR' has path length of 2, because we are just iterating the string and moving either left or right based on the input.

---------------------------------------------------------------------------------------------------------------

class PriorityQueue:

    def __init__(self):

        self.bin_heap = [0]

        self.current_size = 0

    def insert(self,k):

        self.bin_heap.append(k)

        self.current_size = self.current_size + 1

        self.perc_up(self.current_size)

    def build(self,k):

        for i in k:

          self.bin_heap.append(i)

          self.current_size = self.current_size + 1

       

        index = self.current_size;

        while index>=1:

          self.perc_up(index-1)

          index = index-1

       

    def perc_up(self,i):

        while i // 2 > 0:

            if self.bin_heap[i] < self.bin_heap[i // 2]:

                tmp = self.bin_heap[i // 2]

                self.bin_heap[i // 2] = self.bin_heap[i]

                self.bin_heap[i] = tmp

            i = i // 2

    def perc_down(self,i):

        while (i * 2) <= self.current_size:

            mc = self.min_child(i)

            if self.bin_heap[i] > self.bin_heap[mc]:

                tmp = self.bin_heap[i]

                self.bin_heap[i] = self.bin_heap[mc]

                self.bin_heap[mc] = tmp

            i = mc

    def end_of_path(self,string):

      if len(string)==0:

        return self.bin_heap[1]

      index = 0

      k = 1

      while index < len(string):

        if string[index] =='L':

          path = 2*k

        else:

          path = 2*k + 1

       

        index = index + 1

        k = path

      if path<=self.current_size:

        return self.bin_heap[path]

      else:

        return None

values = [1]

pq = PriorityQueue()

for i in values:

pq.insert(i)

print(pq.end_of_path(''))

values = [1,2,3,37,6,5]

pq = PriorityQueue()

for i in values:

pq.insert(i)

print(pq.end_of_path('LR'))

--------------------------------------------------------------------------------------------

SEE OUTPUT




Thanks, PLEASE COMMENT if there is any concern.

saved main.py http://PiercingMusty Files def end_of_path(self, string): if len(string)0: return self.bin_heap [1] 40 Python 3.6.1 (def [GCC 4.8.2] on li main.py 41 42 1 43 index= 0 k 1 44 while index < len(string): if string[index] =='L': 45 46 47 path 2*k 48 else: path 2*k + 1 49 50 index = index + 1 51 52 k = path 53 54 if path<=self.current_size: return self.bin_heap [path] 55 else: 56 57 return None 58 values =[1] pq PriorityQueue() 59 60 61 for i in values: pq.insert(i) print (pq.end_of_path('')) 62 63 64 values [1,2,3,37,6,51 pq PriorityQueue ( ) 65 66 for i in values: 67 68 pq.insert(i) print (pq.end_of_path('LR') 69