title: Insertion of a new element in Binary Max Heap
body: <p>Consider the process of inserting an element into a MaxHeap, where the MaxHeap is represented by an array. Suppose we perform a binary search on the path from the new leaf to the root to find the position for the newly inserted element, the number of comparisons performed is:</p>
  
  <p>A) Θ(logn)</p>
  
  <p>B) Θ(loglogn)</p>
  
  <p>C) Θ(n)</p>
  
  <p>D) Θ(nlogn)</p>
  
  <p>=========================================================================</p>
  
  <p>Let's say I took Max Heap as </p>
  
  <pre><code>                               100
                                /    \
                              80       90
                              /\       /\
                             50 40    70 60
  </code></pre>
  
  <p>and now say I inserted a new element 250 which will be added at last leaf node as shown below - </p>
  
  <pre><code>                                100
                                /    \
                              80       90
                              /\       /\
                             50 40    70 60
                             /
                            250
  </code></pre>
  
  <p>and now by adding 250 max heap property gets violated and I've to call Max heaping which will take O(log n), but my question is now array is not SORTED as you can see from max heap, then how can we apply Binary search at all?</p>
  
  <p>See the array is 100|80|90|50|40|70|60|250 and from leaf to root the path<br>
  contain nodes as <strong>100|80|50|250</strong> and this is not a sorted array, So, how we can apply Binary search?</p>
  
  <p>Another Take - Should I've added a new element which will not violate the max heap property say I add new element 30, then array will be sorted in descending order and I can apply Binary search. </p>
  
  <p>So, how should I tackle this in exam?</p>