title: Deleting a random element from a heap
body: <p>I read a few articles which said that, in a heap, only the root element can be deleted. However, why can't we delete elements, using the below approach?</p>
  
  <ol>
  <li>Find the index of the key element you want to delete</li>
  <li>Swap this element with the last element, so the key becomes the last element</li>
  <li>Re-heapify starting at the original index of the key(which you have now swapped with the last element)</li>
  <li>Reduce size of heap by 1</li>
  </ol>
  
  <p>So, the code would look like</p>
  
  <pre><code>static void delete(int[] a, int key)
      {
          int i = 0;
          for(i = 0;i&lt;a.length;i++)
          {
              if(a[i] == key)
                  break;
          }
          swap(a, i, a.length-1);
  
          max_heapify_forheapsort(a, i, a.length-2);
      }
  
  static void max_heapify_forheapsort(int[] a, int i, int limit)
      {
          int left = (2*i)+1;
          int right = (2*i) + 2;
          int next = i;
  
          if(left &lt;= limit &amp;&amp; a[left] &gt; a[i])
              next = left;
          if(right &lt;= limit &amp;&amp; a[right] &gt; a[next] )
              next = right;
  
          if(next!=i)
          {
              swap(a, next, i);
              max_heapify_forheapsort(a, next, limit);
          }
      }
  </code></pre>