algorithm - replacing element in min-heap

Question

this ques. was asked to my friend in phone interview .

Implement a function that will replace element at index i by k , 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 .

Answer 1

Something like solution 1 is probably better.

• heap[i] = k
• If heap[i] is smaller than its parent, bubble it up (swim)
• Otherwise, if heap[i] is larger than one of its children, bubble it down (sink)

Running time: O(log n).

To swim - While it's smaller than its parent, swap it with its parent.

To sink - While it's larger than one of its children, swap it with its smallest child.

Some Java code for sink and swim, taken from here:

private void swim(int k) {
   while (k > 1 && less(k/2, k)) {
      exch(k, k/2);
      k = k/2;
   }
}

private void sink(int k) {
   while (2*k <= N) {
      int j = 2*k;
      if (j < N && less(j, j+1)) j++;
      if (!less(k, j)) break;
      exch(k, j);
      k = j;
   }
}