python question The initialisation function and the __str__() function for a Pri
ID: 3903540 • Letter: P
Question
python question
The initialisation function and the __str__() function for a PriorityQueue class are shown below. This class uses a min binary heap (i.e. the smallest value at the root), stored in a Python list, to represent the priority queue. class PriorityQueue:
def __init__(self):
self.bin_heap = [0]
self.current_size = 0
def __str__(self):
return str(self.current_size) + " : " + str(self.bin_heap[1:])
A PriorityQueue object, pq, has been created and has had the following six values inserted, in this order: 30, 20, 15, 12, 13, 18 The code for performing these insertions is as follows:
pq = PriorityQueue()
pq.insert(30)
pq.insert(20)
pq.insert(15)
pq.insert(12)
pq.insert(13)
pq.insert(18)
What is the output after each of the following statement are executed, in the order shown below (note that in each question, the first part of the output string - the size of the priority queue - is already shown)?
a) printing the current priority queue print(pq) 6 :
b) then, continuing after (a), inserting the value 17 and printing the resulting priority queue: pq.insert(17) print(pq) 7 :
c) finally, continuing after (b), deleting the minimum value from the priority queue, and then printing the remaining values: pq.del_min() print(pq) 6 :
Explanation / Answer
Hello Student!
I am happy to help you there.
Part a) Printing the current priority queue print(pq) will give me the output
12, 13, 18, 15, 20, 30
Binary heap that is formed will look like :
12 will be the root node 12->left = 13 and 12->right = 15
For, 13->right = 20 and 13-> left = 15
For, 18->left = 30
12
13 18
15 20 30
Now, coming over to the second part
b) When we insert 17 to the priority queue
It becomes -
12, 13, 15, 17, 18, 20, 30
12
13 15
17 18 20 30
12 will be the root node 12->left = 13 and 12->right = 15
13->left = 17 and 13->right = 18
15->left = 20 and 15->right = 30
C) Continuing it, deleting the minimum will give us output :
13, 15, 17, 18, 20, 30
13
15 17
18 20 30
13 will be the root node 13->left =15 and 13->right = 17
15->left = 18 and 15->right = 20
17->left = 30
Thank you. Feel free to ask anything. I have answered all the questions which were asked. I would be happy to assist you further. Please, upvote the answer if you like it. Thank you again.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.