Problem Submissions Solution

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.

Topics

Companies

Articles

Examples:

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)

Constraints:
  • 1 <= Q <= 10^4
  • 1 <= x <= 10^4
Companies:
Amazon Microsoft Samsung Walmart
Topics:
Heap
Locked Content
Access Restricted: Please Login to access the code editor and test cases.