In an array-based implementation of a heap,the number of array items that must be swapped to transform a semiheap of n nodes into a heap is ______.
A)n
B)n + 1
C)log2ⁿ
D)log2(n + 1)

Question

Quizplus · Accepted Answer

In a heap, if the parent node is smaller than the child node, the parent and child nodes must be swapped. Therefore, we can start from the halfway point of the array, which is the parent node of the last leaf node, and check the parent and child nodes to see if they need to be swapped. We can then move up the tree until we reach the root node. At each level of the tree, the number of nodes that need to be checked and, if necessary, swapped is half of the nodes at the level below it. Therefore, the number of swaps required is proportional to the height of the tree, which is log2(n+1) for a heap of n nodes. Thus, the answer is D.

In an Array-Based Implementation of a Heap,the Number of Array