140. Implement Min Heap
You need to implement the Min Heap with the following given methods.
- insert (x) -> insert value x to the min heap
- getMin -> Output the minimum value from min heap
- exctractMin -> Remove the minimum element from the heap
- heapSize -> return the current size of the heap
- isEmpty -> returns if heap is empty or not
- changeKey (ind, val) -> update the value at given index to val (index will be given 0-based indexing)
- initializeHeap -> Initialize the heap
Example 1:
Input : operation = [ "initializeheap", "insert", "insert", "insert", "getMin", "heapSize", "isEmpty", "extractMin", "changeKey" , "getMin" ]
nums = [ [4], [1], [10], [0, 16] ]
Output : [ null, null, null, null, 1, 3, 0, null, null, 10 ]
Explanation : In 1st operation we initialize the heap to empty heap.
In 2nd, 3rd, 4th operation we insert 4, 1, 10 to the heap respectively. The heap after 4th operation will be -> [1, 4, 10].
In 5th operation we output the minimum element from the heap i.e. 1.
In 6th operation we output the size of the current heap i.e. 3.
In 7th operation we output whether the heap is empty or not i.e. false (0).
In 8th operation we remove the minimum element from heap. So the ne heap becomes -> [4, 10].
In 9th operation we change the 0th index element to 16. So new heap becomes -> [16, 10]. After heapify -> [10, 16].
In 10th operation we output the minimum element of the heap i.e. 10.
Now Your Turn!
Pick the correct output for the given inputInput : operation = [ "initializeheap", "insert", "insert", "extractMin", "getMin", "insert", "heapSize", "isEmpty", "extractMin", "changeKey" , "getMin" ]
nums = [ [4], [1], [1], [0, 2] ]
Output : [ null, null, null, null, 4, null, 2, 0, null, null, 2 ]
Explanation : In 1st operation we initialize the heap to empty heap.
In 2nd, 3rd operation we insert 4, 1 to the heap respectively. The heap after 4th operation will be -> [1, 4].
In 4th operation we remove the minimum element from heap. So the ne heap becomes -> [4].
In 5th operation we output the minimum element of the heap i.e. 4.
In 6th operation we operation we insert 1 to the heap. The heap after 6th operation will be -> [1, 4].
In 7th operation we output the size of the current heap i.e. 2.
In 8th operation we output whether the heap is empty or not i.e. false (0).
In 9th operation we remove the minimum element from heap. So the ne heap becomes -> [4].
In 10th operation we change the 0th index element to 2. So new heap becomes -> [2].
In 11th operation we output the minimum element of the heap i.e. 2.
Still unsure what the problem is asking ?
Let’s go through a few more examples, step by step, to make it clearer.
Constraints:
- 1 <= n <= 105
- -105 <= nums[i] <= 105