Minimum / Maximum Maintenance algorithm implementation using JavaScript / TypeScript

Assume that you are given numbers slowly, one by one. At any point, you can be asked to give the numbers back in ascending order. The first extraction should give you two. The second extraction should give you three. If I give you another number, you should continue to extract the minimum of the current remaining numbers.

We can code this up into a minimum array data structure quite easily and intuitively. We go ahead and create a class for this. Here, we'll be storing the data internally in a number array. Whenever you are requested to add an item, we loop through all the existing items, and insert it into the array in descending order.

Finally, we return, and if all the items existing in the array were larger, we simply push the item at the end. Now, since we might end up looping through all the elements in the array, this add operation has a time complexity of O(n).

For extracting the minimum, we now simply need to return the last item in the array, which we can do through array prototype pop method, which has a time complexity of O(1). Note that we can simply change this data structure to maintain the maximum value instead of the minimum by simply changing the comparison operation within our add method.

We go ahead and inherit from this class, and replace the add method with a new one. Now, let's use these classes in a simple sample. We create a minimum array, add some items into it, and I iteratively extract the minimum, logging it out at each point.

If you go ahead and run this example, you can see that it works as expected, extracting the minimums turn by turn, one, two, four, five. We can also run this example for the maximum by simply changing which data structure we initialize.

Again, it works as expected. The complexity of the whole add/extract cycle is driven by the complexity of the add operation, which is O(1). Doing this operation for n items results in an O(n²) time complexity, and we can do better.

The simple trick here is to remember that there is a data structure designed for the specific problem of repeated minimum or maximum computations. This data structure is called the heap, and we have looked at it in a previous lesson.

In fact, the heap data structure is so well-suited to this problem that we will not even bother wrapping it in a class. We simply import the heap data structure, initialize it, passing in a comparison function that sorts in ascending order, giving us a min heap. Instead of extract, we now use the heap's extractRoot method.

When we go ahead and run it, you can see that it works as expected, giving us the repeated minimums, one, two, four, five. The behavior is similar to the minimum array, however now the add operation is log(n), therefore the runtime has gone from n² to n*log(n).

As always, we can always easily change the behavior to the max heap by swapping the arguments to the comparison function, giving us the same behavior as a maximum array, but with better overall time complexity across the sum of the add and extract operations.