InstructorBasarat Ali Syed

Published 7 years ago

Updated 3 years ago

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.

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.

egghead

~ 4 minutes ago

Markdown supported.

Become a member to join the discussionEnroll Today

Member comments are a way for members to communicate, interact, and ask questions about a lesson.

The instructor or someone from the community might respond to your question Here are a few basic guidelines to commenting on egghead.io

Be on-TopicComments are for discussing a lesson. If you're having a general issue with the website functionality, please contact us at support@egghead.io.

Avoid meta-discussionCode Problems?Should be accompanied by code! Codesandbox or Stackblitz provide a way to share code and discuss it in context

Details and ContextVague question? Vague answer. Any details and context you can provide will lure more interesting answers!