A min-priority-queue is a data structure that you can insert element to it and delete element from it. However, you can't delete arbitrary element in a min-priority-queue, you can only delete the element with minimum value in it. Similarly, you can only delete the element with maximum value in a max-priority-queue.
In this problem, you are going to maintain a min-priority-queue and a max-priority-queue, which support the following operations:
INSERT val: Insert a element val to both min-priority-queue and max-priority-queueDELETE M: Delete an element from the max-priority-queueDELETE m: Delete an element from the min-priority-queueITER M: Print out the elements in the max-priority-queue, in insertion orderITER m: Print out the elements in the min-priority-queue, in insertion orderINTER: Print how many number are both in the min-priority-queue and the max-priority-queue Originally, both max-priority-queue and min-priority-queue are empty.
Given the template:
from abc import ABC, abstractmethod
class BasicPQ(ABC):
def __init__(self):
self.data = list()
def insert(self, val):
# TODO
# insert an element with value val into the priority queue
raise NotImplementedError
@abstractmethod
def delete(self):
raise NotImplementedError
def __iter__(self):
self.index = 0
return self
def __next__(self):
# TODO
# if there is a next (in the insertion order) value in self.data, return it and increase self.index
# otherwise, raise StopIteration
raise NotImplementedError
class MinPQ(BasicPQ):
def delete(self):
# TODO
# delete the minimum value in the priority queue
raise NotImplementedError
class MaxPQ(BasicPQ):
def delete(self):
# TODO
# delete the maximum value in the priority queue
raise NotImplementedError
def Inter(max_pq, min_pq):
# TODO
# return the number of elements that are in both min-priority-queue and max-priority-queue
rase NotImplementedError
# DO NOT change the code below
num_ops = int(input())
min_pq = MinPQ()
max_pq = MaxPQ()
for i in range(num_ops):
op = input().split()
if op[0] == "INSERT":
val = int(op[1])
min_pq.insert(val)
max_pq.insert(val)
elif op[0] == "DELETE":
if op[1] == "M":
max_pq.delete()
else:
min_pq.delete()
elif op[0] == "ITER":
if op[1] == "M":
it = iter(max_pq)
print("Elements in the max-priority-queue:", end=' ')
for i in it:
print(i, end=' ')
print()
else:
it = iter(min_pq)
print("Elements in the min-priority-queue:", end=' ')
for i in it:
print(i, end=' ')
print()
elif op[0] == "INTER":
print(Inter(max_pq, min_pq))
The first line contains an integer T (T <= 1000), representing the number of operations
For the next T lines, each line contain one of an operation above.
The constraints of each operations:
INSERT val: val <= 1000, all vals are distinctDELETE M: It is guaranteed that the max-priority-queue must be non-emptyDELETE m: It is guaranteed that the min-priority-queue must be non-emptyITER M: It is guaranteed that the max-priority-queue must be non-emptyITER m: It is guaranteed that the min-priority-queue must be non-emptyINTER: No extra constraintFor each following operation, output the corresponding text:
ITER M: Output Elements in the max-priority-queue: , followed by the elements in the max-priority-queue. A space should be added right after each element.ITER m: Output Elements in the min-priority-queue: , followed by the elements in the min-priority-queue. A space should be added right after each element.INTER: Output a number, representing the number of elements that are both in the min-priority-queue and the max-priority-queue