Question
In the context of this exercise, how many swaps are needed when adding a node to a heap?
Answer
The number of swaps needed when adding a node can range from 0 to the height of the heap. 0 swaps are needed if the node is added in the correct position initially without any swaps necessary.
The height of a heap can best be visualized using the binary tree illustration. The height is the longest continuous edge from the root node to the bottom-left-most node. We can calculate this value using the log() function as well.
For any heap of size N, the height is
floor(log base 2 of N)
For example, if we have 4 elements in our heap, then the height is
floor(log base 2 of 4) which is 2.
And if we had 7 elements in our heap, then the height would be
floor(log base 2 of 7) which is 2 as well.
Feel free to draw some heaps and use this calculation to check if it returns the correct height for each. When doing so however, keep in mind that the heaps must be constructed from left to right with each layer filled before a new layer is added, to maintain the correct structure.