To add a new element X to a heap:
A) if the tree is empty,make X the root of a new tree;otherwise,compare X to the root,if X is less,put it in the left subtree,if it is greater,put in the right subtree
B) First add X in the position of the root.If X is a leaf,or is less than its children,stop.Otherwise,repeatedly swap X with the smaller of its two children until X becomes a leaf,or becomes less than its children.
C) Add X as a leaf,taking care to preserve the completeness of the heap.If X is now the root,or is greater than its parent,stop.Otherwise,repeatedly swap X with its parent until X becomes the root,or becomes greater than its parent.
D) insert X using the same algorithm for insertion in a binary search tree.If the tree remains balanced,stop.Otherwise,execute a rebalancing operation.

Question

Quizplus · Accepted Answer

Choice C is the best option because it ensures that the heap remains complete while also maintaining the heap property. It starts by adding X as a leaf and then swaps it with its parent until it becomes the root or is greater than its parent. This approach is efficient and requires fewer swaps than option B. Options A and D are not optimal because they do not guarantee that the heap property is maintained after adding the new element.

To Add a New Element X to a Heap