Consider the PriorityQueue class given below:

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 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 min_child(self,i): if i * 2 + 1 > self.current_size: return i * 2 else: if self.bin_heap[i*2] < self.bin_heap[i*2+1]: return i * 2 else: return i * 2 + 1 def del_min(self): retval = self.bin_heap[1] self.bin_heap[1] = self.bin_heap[self.current_size] self.current_size = self.current_size - 1 self.bin_heap.pop() self.perc_down(1) return retval def __str__(self): return str(self.bin_heap)

Q1:

Insert a function named build(self, list) which builds a priority queue from a list. You should use the method 2 from the lecture handout. Insert elements into the self.bin_heap and change the current_size and then re-arrange the elements starting from the first element which has a child and keep rearranging (i.e., perc_down()) working backwards towards the first element.

For example:

Test	Result
pq = PriorityQueue() keys = [9, 5, 8, 6, 3, 2] pq.build(keys) print(pq)	[0, 2, 3, 8, 6, 5, 9]

Q2:

Insert a function named findk(self, k) which returns a list of the k-th smallest value in a binary heap. The function should check if there are more than k-element inside the heap, then calling del_min() k times to get first the smallest item from the priority queue, then the next smallest, and so on.

For example:

Test	Result
pq = PriorityQueue() keys = [9, 5, 8, 6, 3, 2] for k in keys: pq.insert(k) print(pq.findk(4))	[2, 3, 5, 6]