Heap Sorting Algorithm

Goals

Students will understand elements of the heap sort algorithm, which incrementally removes cards in sorted order from a heap.

Video

Materials

One deck of Acorn cards.

this is a placeholder image — Sample cards from the Acorn deck.

Setup

Shuffle the deck and deal each student 9 cards.

Each student will shuffle their 9 cards, and then create a heap as demonstrated on the insertion algorithm page.

Algorithm

The heap sort algorithm uses the same basic steps from the removal algorithm, in order to turn a heap into a sorted collection.

The first step in the heap sort algorithm is to remove the smallest card from the heap as demonstrated on the removal algorithm page. This card will be the start of your collection.

Repeat the previous step, adding each least-card to your collection, until there are no more cards in the heap. When you are finished all of the cards in your collection should be in sorted order, with the smallest on the left and the largest on the right.

Example

We’ll start with the example heap from the insertion algorithm page.

Our next step is to apply the removal algorithm to our heap. The root card 03 is removed and is the first card in our collection. The removal algorithm ensures our heap stays in minimum order and that the next root card will be the smallest value in the heap.

There are still cards in the heap, so we repeat the previous step and apply the removal algorithm to our heap. The root card 03 is removed and is the next card in our collection.

Card 03 added to the collection — Card 03 is added to the collection

There are still cards in the heap, so we repeat the previous step and apply the removal algorithm to our heap. The root card 15 is removed and is the next card in our collection.

Card 15 added to the collection — Card 15 is added to the collection

There are still cards in the heap, so we repeat the previous step and apply the removal algorithm to our heap. The root card 16 is removed and is the next card in our collection.

Card 16 added to the collection — Card 16 is added to the collection

There are still cards in the heap, so we repeat the previous step and apply the removal algorithm to our heap. The root card 25 is removed and is the next card in our collection.

Card 25 added to the collection — Card 25 is added to the collection

There are still cards in the heap, so we repeat the previous step and apply the removal algorithm to our heap. The root card 31 is removed and is the next card in our collection.

Card 31 added to the collection — Card 31 is added to the collection

There are still cards in the heap, so we repeat the previous step and apply the removal algorithm to our heap. The root card 36 is removed and is the next card in our collection.

Card 36 added to the collection — Card 36 is added to the collection

There are still cards in the heap, so we repeat the previous step and apply the removal algorithm to our heap. The root card 48 is removed and is the next card in our collection.

Card 48 added to the collection — Card 48 is added to the collection

There are still cards in the heap, so we repeat the previous step and apply the removal algorithm to our heap. The root card 56 is removed and is the next card in our collection.

Card 56 added to the collection — Card 56 is added to the collection

There are still cards in the heap, so we repeat the previous step and apply the removal algorithm to our heap. The root card 66 is removed and is the next card in our collection.

Root card 66 removed from heap and added to the collection

The collection should now be in sorted order, and we are finished.