This Lesson is for Members

Subscribe today and get access to all lessons! Plus direct HD download for offline use, enhances transcripts, member comment forums, and iTunes "podcast" RSS feed. Level up your skills now!

Unlock This Lesson

Already subscribed? Sign In

Autoplay

    Minimum / Maximum Maintenance algorithm implementation using JavaScript / TypeScript

    Basarat Ali SyedBasarat Ali Syed

    How can you most efficiently maintain the lowest value in a list of items. How about maintaining the largest value?

    In this lesson we cover a naïve solution to this problem followed by an efficient solution that utilizes a data structure we have already covered before.

    typescriptTypeScript
    Code

    Code

    Become a Member to view code

    You must be a Member to view code

    Access all courses and lessons, track your progress, gain confidence and expertise.

    Become a Member
    and unlock code for this lesson
    Transcript

    Transcript

    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.

    Discuss

    Discuss