In an array-based implementation of a heap,the heapInsert operation is ______.
A)O(1)
B)O(n)
C)O(n²)
D)O(log n)

Question

Quizplus · Accepted Answer

In an array-based implementation of a heap, the heapInsert operation inserts a new element at the last index of the heap's underlying array and then has to rearrange the heap to maintain the heap property. This rearranging takes place by comparing the new element with its parent and swapping them if necessary until it reaches the correct position in the heap. The number of swaps required during this rearrangement is proportional to the height of the heap, which is log n for a heap of n elements. Therefore, the time complexity of heapInsert in an array-based implementation is O(log n).

In an Array-Based Implementation of a Heap,the HeapInsert Operation Is