ScholarHat
ScholarHat
0
Live Batches
Masterclasses
Menu
Free Courses
Account
Login / Sign Up

Binary Heap Operations

Medium Acceptance 22.3% Points 30
Topics Hints Companies

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.
Examples
Example 1

Example 1

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.

Constraints
  • 1 <= Q <= 10^4
  • 1 <= x <= 10^4
Hints
  • Expected Time Complexity: O(Q*Log(size of Heap))
  • Expected Auxiliary Space: O(1)
Topics
Heap
Companies
Amazon Microsoft Samsung Walmart
Added 01 May 2025 22.3% acceptance
Ln 1, Col 1Sign in to save your code
6
1 5
1 3
1 10
3
2 3
3
3 5