11.1.2. Using Heaps for Sorting

So, before we leave heaps, let us see how to use heaps to sort. So, we want to sort a list of values. So, what we can do is, we can first build a heap, right. So, we now start with some arbitrary sequence of values, x 1 to x n, then we build a heap and we possibly get reordered in some way of x i 1, x i 2, x i n, but this is not in sorted way, this is in a heap structure.

To sort a list of values using heaps, the first step is to build a heap from the arbitrary sequence of values. A heap is a binary tree where each parent node is either greater than (in a max heap) or less than (in a min heap) its child nodes. When we build a heap from the values x1 to xn, they are arranged according to this property, ensuring that the maximum or minimum is easily accessible but not necessarily sorted.

Think of this heap-building process like organizing a collection of toys in a box where some toys are stacked on top of others. The largest toy is always at the very top, making it easy to retrieve when needed, but the toys beneath are not arranged in any specific order.

Now, I do delete max and I put this guy out, right. So, I know that this is the maximum. Then, after this, something will come to the front. At the next point, that will come out, and then I will get the second max and so on, right. So, if I do delete max n times, clearly, at each point I get the next maximum.

After building the heap, the next step is to repeatedly extract the maximum value using the delete max operation. Each time we delete the maximum value, it gets removed from the heap, and a new maximum value takes its place. By performing this delete max operation n times, we obtain a sequence of maximum values in descending order. This means that after all operations are complete, we have effectively sorted the original list.

Imagine a game where you are trying to find the tallest person in a line of friends. Each time you identify the tallest (maximum), you ask them to step aside while the others adjust their positions. Eventually, after many rounds, you have arranged everyone by height, from tallest to shortest, similar to how we sort values from a heap.

So, therefore, I can, in fact, at this point go and put this value back into the heap at this position and ensure it is not much, right. So, now what will happen is, I will have the max coming here, then I will have the next second max coming here and so on.

Instead of removing the maximum values from the heap and placing them into a new array, we can place them into the same array where the heap is stored, utilizing the empty spaces created by the extracted values. As we continue to delete the maximum values, we fill in the original list from the back towards the front, leading to a sorted output in-place.

Consider a stack of plates where the top plate is the largest and you need to remove plates one by one. Instead of setting the removed plates aside completely, you start placing them neatly back onto an already emptied shelf. As you remove each plate, the next largest plate drops into place. By the time you've gone through all plates, the shelf is arranged from largest to smallest.

So, overall we sorted in n log n time.

The time complexity of sorting using heaps is O(n log n). Building the heap initially takes linear time, O(n), because we are essentially processing each element once. Each delete max operation is logarithmic, O(log n), due to the height of the heap. Since we perform this delete operation n times, we end up with n log n as the overall time complexity for the sorting operation.

You can think of this sorting process like organizing a large event. Setting everything up at first (building the heap) might take some time, but once it's established, adjusting the seating arrangements (removing and replacing maximum values) takes a predictable amount of effort logistically. Therefore, even a big event can be organized efficiently.

--