MAX-HEAP increase key procedure

Question

In the max heap Increase key procedure

IncreaseKey(int pos, int newValue)
{
   heap[pos] = newValue;
   while(left(pos) < heap.Length)
   {
      int smallest = left(pos);
      if(heap[right(pos)] < heap[left(pos)])
         smallest = right(pos);
      if(heap[pos] < heap[smallest])
      { 
         swap(smallest, pos);
         pos= smallest;
      }
      else return;
   }   
}

When the Max heap property is violated at a node x, we dont call MAX-HEAPIFY procedure to mend the Max-heap property, What is the reason behind it?

Answer 1

That work is already done is while loop.

We are comparing the increased key value with its parent. If it is greater than parent we swap them. This continues till we find a parent is greater than child compared.

Take an example and trace out the steps, it will help in understanding.

Comments

time complexity will be O(logn) right?

---

Yes. Time Complexity is O(logn)