PYTHON:

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) 

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.

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

pq = PriorityQueue() keys = [21,84,14,51,63,68,6,95] pq.build(keys) print(pq)

[0, 6, 51, 14, 84, 63, 68, 21, 95]