Question: You are given a data structure H that currently stores N distinct integers. H supports an operation minmax() that removes either the minimum or the
You are given a data structure H that currently stores N distinct integers. H supports an operation minmax() that removes either the minimum or the maximum number in it in constant time. You will know the number, but you won't know if it was maximum or minimum when it got removed. Using minmax(), write a pseudo-code to output the numbers from H in a sorted order into an array of length N. You are not allowed to use additional data structures/arrays for storage, but you may use variables for additional storage. You are also not allowed to sort the output array directly; so, the complexity should be O(N).
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
