this ques. was asked to my friend in phone interview .
Implement a function that will replace element at index
i
byk
, in min-heap and rearrange heap back .
here is my solution , please tell if i am right or not.
solution 1 :
1)heap[i]=k
2) heapify(heap , 1)
but this seems to be wrong as in this case :
10
/
14 59 (<-was 12 before replacing)
.. /
55 20
so here we swap(55,59) but still min-heap property will be voilated.
solution 2:
1)replace heap[i] by heap[last index]
2) heapify(heap , 1)
3) now insert as usual procedure in heap
time complexity - O(log N)
is it (solution 2) the correct approach ? if not please give some hints
.