CS 10C Programming Concepts and Methodologies 2

Draw the array along with the tree diagram tracing the steps to sort the following list of numbers using heapsort.

33 20 4 0 36 5

To do this correctly you must view the lecture video demonstration. You must draw the array and tree diagram every time a swap is performed! I realize that this may be a bit tedious, but it's important.

Here is an algorithm you can follow. I'm hoping this will help, but if it's easier to just follow along with the example in the lecture, that's fine too. Note that Every time you do a swap or highlight an item, you must do it in both the array and the corresponding tree diagram.

Draw the original diagram;
while (array does not represent a heap) {
    Copy/paste the diagram;
    Perform the next required swap;
}

while (some nodes other than the root remain un-highlighted) {
    Copy/paste the diagram;
    if (the array represents a heap) {
        Swap array[0] with the last unhighlighted item in the array;
        highlight that item.
    } else {
        Perform the next required swap;
    }
}

The solution will have 13 swaps (thus, 14 copies of the diagram).