Binary Heap Operations
Difficulty: Medium
Acceptance: %
Points: 30.00
You are given an initially empty Binary Min Heap and a series of queries. Your task is to implement three methods: insertKey, deleteKey, and extractMin on the Binary Min Heap, and call them as per the query given below:
- 1 x - This query inserts the element x into the min-heap.
- 2 x - This query removes the element at position x from the min-heap.
- 3 - This query removes and prints the minimum element from the min-heap.
Input: Q = 6, Queries: insertKey(10) insertKey(5) insertKey(15) extractMin() deleteKey(1) extractMin()
Output: [5, 10]
Explanation: insertKey(10): The heap starts empty. After inserting 10, the heap becomes {10}. insertKey(5): Inserting 5 results in the heap {5, 10} since 5 is the smaller element. insertKey(15): Inserting 15 results in the heap {5, 10, 15}. extractMin(): The minimum element 5 is removed from the heap, leaving {10, 15}, and 5 is printed. deleteKey(1): The element at position 1 (which is 15) is removed, leaving {10}. extractMin(): The minimum element 10 is removed, and 10 is printed. The heap is now empty.
Expected Time Complexity: O(Q*Log(size of Heap))
Expected Auxiliary Space: O(1)
- 1 <= Q <= 10^4
- 1 <= x <= 10^4
