Chapter 16
These are the solutions to the exercises found in the section .
-
After inserting an 11, the heap would look like this:
-
After deleting the root node, the heap would look like this:
-
The numbers would be in perfect descending order. (This is for a max-heap. For a min-heap, they’d be in ascending order.)
Do you realize what this means? It means you’ve just discovered another sorting algorithm!
Heapsort is a sorting algorithm that inserts all the values into a heap and then pops each one. As you can see from this exercise, the values always end up in sorted order.
Like Quicksort, Heapsort is O(N log N). This is because we need to insert N values into the heap, and each insertion takes log N steps.
While there are fancier versions of Heapsort that try to maximize its efficiency, this is the basic idea.
