HackerRank DSA Solutions Tutorial

QHeap1| Heap

❮ Previous Next ❯

Task (easy)

This question is designed to help you get a better understanding of basic heap operations.
There are 3 types of query:
"1 " - Add an element v to the heap.
"2 " - Delete the element v from the heap.
"3" - Print the minimum of all the elements in the heap.
NOTE: It is guaranteed that the element to be deleted will be there in the heap. Also, at any instant, only distinct elements will be in the heap.
Input Format
The first line contains the number of queries, Q.
Each of the next lines contains one of the 3 types of query.
Constraints

1 ≤ Q≤ 105
-109 ≤v≤ 109

Output Format
For each query of type 3, print the minimum value on a single line.

Sample Input

STDIN       Function
5           Q = 5
1   4       insert 4
1   9       insert 9
3           print minimum
2   4       delete 4
3           print minimum

Sample Output

Explanation
After the first 2 queries, the heap contains (4, 9). Printing the minimum gives 4 as the output. Then, the 4th query deletes 4 from the heap, and the 5th query gives 9 as the output.

Solution 1

from bisect import insort

class Heap:

    def __init__(self):

        self.heap = []

    def insert(self, val):

        insort(self.heap, val)

    def delete(self, val):

        self.heap.remove(val)

    def minimum(self):

        if self.heap:

            print(self.heap[0])

q = int(input())

heap = Heap()

for _ in range(q):

    query = [int(i) for i in input().split(" ")]

    if query[0] == 1:

        heap.insert(query[1])

    elif query[0] == 2:

        heap.delete(query[1])

    elif query[0] == 3:

        heap.minimum()

❮ Previous Next ❯

HackerRank DSA Solutions Tutorial

HackerRank DSA Solutions Tutorial

HackerRank DSA Solutions

QHeap1| Heap

Important Links