One of the last bit to talk about heap is to really dive into things we can do with a heap. Because what we know right now, is we know that we can do an insert and remove operation by just doing simple tree operations. From our knowledge about trees, we know that these are login operations because we have a complete tree. The other thing we know is we can actually build a heap in O of n time. So, we can build it in linear time, which is a fantastic result, and it leads to us actually doing interesting things with the heap. One thing I want to dive into, is one interesting algorithm you can use by using a heap, and this is the heap sort. So, we'll get on the heap sort, we're going to look at how we can actually build a sorted array by exploiting the fact that we have a heap. Let's dive into this example. Doing a heap sort is going to be three steps. The first step is we want to build a heap, and to build a heap we can do this operation in simply O of n time to create a heap out of a list of elements. The next thing we need to do to actually get at the sorted lists in our heap sort, we need to call n calls of removeMin. So, once we've built the heap in O of n time, we can call removeMin for log n time, each time. So, what this means is, we have a log n operation every n times for n log n runtime. Then only if it's needed, which may not be necessary, we may want to swap elements to order our list in the proper way, either ascending or descending. So, notice that we have a heap and we continually call removeMin. We're going to get at a list that's going to have four as the minimum element, then five, then six, then seven, then nine, and so forth by continually removing minimum from our tree. We know the slowest operation here is built heap which takes n time, but the login time is going to be required for every single removeMin operation. So, in the very worst case, our running time is going to be n times log n because we have n operations of log n time, which is going to dominate the building heap call of O of n time. So, even though we can build a heap in just O of n time, we can actually do what's called a heap sort in an optimal time for sorting in log n time. We care about this sort because it's often going to be very convenient to do this sort entirely in memory. If you're clever about using this zeroth index that we leave completely empty, you can do a heap sort without using any additional space than the space you have in this array. This means as long as have our data in any format that's in an array, a heap sort is going to be an ideal sort that allows us to order the data and provide some benefits for being in-memory, and will give us some advantages if the data structure is already semi-sorted. So, we've figured out how to actually understand what it is to be a minimum heap, we've figured out how to insert into a remove minimum heap, how to remove min from an minimum heap, we understand that running time is a minimum heap, and now we understand some application of a heap in a min sort. So, what we're going to do next is we're going to start using all of these concepts to build something really great. So, next week, we're going to dive into what it means to have one more algorithm, a disjoint set, and then we're going to finish off this semester by going in depth in graphs. Graphs is an amazing data structure that's going to unlock a lot of potential and allow us to solve a lot of really interesting problems. So, I'll see you then.
