## Binary-Heap

Question 1 |

An operator *delete(i)* for a binary heap data structure is to be designed to delete the item in the *i*-th node. Assume that the heap is implemented in an array and *i* refers to the *i*-th index of the array. If the heap tree has depth *d* (number of edges on the path from the root to the farthest leaf), then what is the time complexity to re-ﬁx the heap efﬁciently after the removal of the element?

O(1) | |

O(d) but not O(1) | |

O(2 ^{d}) but not O(d) | |

O(d 2 ^{d}) but not O(2^{d}) |

Question 1 Explanation:

→ If heap has n elements generally it takes O(n) to delete any arbitrary element.

→ Because we first need to find that element, O(n) time

Delete that element O(height) [deleting involves swapping particular element to rightmost leaf and then do heapify on that node].

**but here, we don't need to find that element, because in delete(i), i is index of that element.

Note: Delete time = O(height) = O(d)

→ Because we first need to find that element, O(n) time

Delete that element O(height) [deleting involves swapping particular element to rightmost leaf and then do heapify on that node].

**but here, we don't need to find that element, because in delete(i), i is index of that element.

Note: Delete time = O(height) = O(d)

There is 1 question to complete.