Heap Insertion Algorithm
Goals
Students will understand elements of the insertion algorithm for heaps.
Video
Materials
One deck of Acorn cards.
Setup
Shuffle the deck and deal each student 9 cards.
Each student will shuffle their 9 cards, and place them in a face-down pile to their left.
Algorithm
Flip the top card face-up, and place this card directly in front of you. This card will be known as the root card.
For the remaining cards, flip each one face-up in turn, calling it the flipped card. You will now insert this card into your heap at the next available spot for a child.
Where To Place
Each card can only hold two children cards, one on the upper-left corner, and one on the upper-right corner.
The flipped card should be placed as a child as close to the root as possible. The card where it is placed will be called the parent card. When there are multiple possible parent cards with open corners for a child that at the same level, choose the left-most parent card.
If the parent card has both corners empty, the upper-left corner is filled before the upper-right corner.
Swap If Lower
Once the flipped card has been placed on a parent card, repeat the step below until you have found the final location in the tree.
- If the flipped card is the root, then stop.
- If the flipped card is less than the parent card below it in the tree, swap the two cards and repeat the Swap If Lower steps.
Continue until all cards have been placed.
Example
The first card flipped up is the 31. Place this in front of you to become the root.
The next card flipped up is the 66. This is placed on the only available parent 31, and placed in the upper-left corner.
66 is greater than 31, so there is no need to swap.
The next card flipped up is the 25. This is placed on the closest card to the root, which is the root, making the parent 31, and placed in the upper-right corner.
25 is less than 31, so there we need to swap. After the swap, 25 is the root, so we stop swapping.
The next card flipped up is the 48. There are two available parents, 66 and 31. 66 is the left-most and is chosen as the parent. 48 is placed in the upper-left corner.
48 is less than 66, so there needs to be a swap. After the swap, 48 is greater than 25, so we stop.
The next card flipped up is the 15. There are two available parents, 48 and 31. 48 is the left-most and is chosen as the parent. 15 is placed in the upper-right corner.
15 is less than 48, so there needs to be a swap. After the swap, 15 is less than 25, so we must continue.
15 is less than 25, so we must swap. After the swap, 15 is the root, so we stop swapping.
The next card flipped up is the 36. There is one available parent, 31, and is chosen as the parent. 36 is placed in the upper-left corner.
36 is greater than 31, so there is no need to swap.
The next card flipped up is the 03. There is one available parent, 31, and is chosen as the parent. 03 is placed in the upper-right corner.
03 is less than 31, so there needs to be a swap. After the swap, 03 is less than 15, so we must continue.
03 is less than 15, so we must swap. After the swap, 03 is the root, so we stop swapping.
The next card flipped up is the 56. There four available parents, 66, 48, 36, and 31. 66 is the left-most and is chosen as the parent. 56 is placed in the upper-left corner.
56 is less than 66, so there needs to be a swap. After the swap, 56 is greater than 25, so we stop.
The next card flipped up is the 16. There four available parents, 56, 48, 36, and 31. 56 is the left-most and is chosen as the parent. 56 is placed in the upper-right corner.
16 is less than 56, so there needs to be a swap. After the swap, 16 is less than 25, so we must continue.
16 is less than 25, so there needs to be a swap. After the swap, 16 is greater than 03, so we stop.
