HEAPEDU3 - Editorial

editorial
, , ,
1

Problem Link - Insertion and deletion together in a Heap Practice Problem in Heaps

Problem Statement

Write a program to perform the following operations:

  • Initialize an array
  • Given an integer N, perform N queries over this array
  • Given a query “+ x”, insert x in your array.
  • Given a query “-”, remove the maximum element of the array.
  • After each query print the maximum element left in the array.

Approach

  • Handling Operations: For each query:
    • Insert operation (+ x):
      • Add x to the max-heap.
      • See this for insert operation - Insertion in a Heap Practice Problem in Heaps
      • After the insertion, the max-heap property ensures that the maximum element is always at the top.
      • Print the element at the top of the heap (the current maximum).
    • Remove maximum operation (- x):
      • Remove the root element (maximum element) from the heap.
      • See this for delete operation - Deletion in a Heap Practice Problem in Heaps
      • After the removal, the max-heap property is restored, and the next largest element becomes the new root.
      • Print the new maximum element (or -1 if the heap is empty).
  • Edge Case Handling: If the heap is empty when attempting to remove the maximum, we should output -1 to indicate the array has no elements left.

Complexity

  • Time Complexity: Each insertion involves adding the new element at the end of the heap and then restoring the max-heap property by moving it up. In the worst case, O(log N) time. Removing elements also require O(log N) time. So for N queries total time complexity will be O(N log N).

  • Space Complexity: The heap vector in the MaxHeap class stores all the elements in the heap. In the worst case, if we perform N insert operations, the heap vector will store N elements. It will be O(N).