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;
   }
}

Answer 2

Here is a way to do that in O(logn)

pseudo code for following operation:-

void replaceHeap(int index,int value) {

  heap[index] = value;
  BubbleUp(index);

  Heapify(index);


}

void BubbleUp(int index) {

   parent = index/2;

   while(index>1&&heap[parent]>heap[index]) {

         swapElementAt(parent,index);
         index = parent;
         parent = index/2;
   }

}

Heapify is standard as you have done it

Answer 3

Here's the simplest implementation in python for simplicity sake.

# Replace item
self.heap[index] = something_new

# Get left child
try:
    left_child = self.heap[2 * index + 1]
except IndexError:
    left_child = None

# Get right child
try:
    right_child = self.heap[2 * index + 2]
except IndexError:
    right_child = None

# Get parent
parent = self.heap[int(math.floor(index / 2))]

# If smaller than parent, swim up
if parent is not None and self.heap[index] < parent:
    swim(index)
    break

# If larger than one of its children sink
if left_child is not None:
    if self.heap[index] > left_child:
        sink(index)
        break

if right_child is not None:
    if self.heap[index] > right_child:
        sink(index)
        break

Answer 4

if it's less than its parent to DecreaseKey(k) else do MinHeapify (k)