Algorithm

Question

Deleting any random element in heap would take n+logn or n+n?

Comments

n+logn

---

@nephron

don't post direct answers, give some explanation on them

if you don't want to give explanation then add in comment section.

---

and it is also not a correct answer

ans will be O(log n)

---

O(log n)??

I think for deleting a random element it should be O(n) @srestha mam!

---

@srestha

mam, it is heap (not BST), how much time to find a element?

---

Oh yes

O(n) to find the element and O(log n) to delete

So, O(n log n)

right?

---

to find O(n) for finding + O(logn) for heapify = O(n)

---

let ,

random number is at index  = randomIndex

To finding the random number = O(n)

A[randomIndex] = A[heap_size]

A.heap_size = A.heap_size-1

heapify (A , randomIndex)

which takes O(log n)

total time : O(n) + O(log n) = O(n)

---

Is it not multiplying requires @Shaik?

because we need both first finding and then heapify operation

It is not an OR operation right?

 

---

No, addition is required not multiplication. U search an element in O(n) and then heapify it O(logn). Nlogn means u r repeating heapify function N times.

---

 @srestha mam

because we need both first finding and then heapify operation

yes, in normal language, but in Algorithms

first loop finds ===>O(n)

second heapify ===> O(log n) 

 

mam, nephron explained it very well

Answer 1

The deletion of random element takes 0(n) + 0(logn) time.

0(n) as the array traverses to find the last element and assign it to the root;

0(logn) as the element swaps as per max/min heap condition and deletion takes for the root.