图解-堆删除节点

秒速五厘米 2022-04-11 04:13 218阅读 0赞

转自：[http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/heap-delete.html][http_www.mathcs.emory.edu_cheung_Courses_171_Syllabus_9-BinTree_heap-delete.html]

*  ***Deleting* a specific node from a *Heap***
    
     
    
     
    
    --------------------
    
    --------------------
    
    --------------------
    
    --------------------
    
     
    
     *  **Problem description:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li>You are&nbsp;<strong>given</strong>&nbsp;a&nbsp;<span style="color:#0000FF;"><strong>heap</strong></span>. <p><strong>For example:</strong></p> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap04.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> 
              <hr><p>&nbsp;</p> </li> 
             <li>You are&nbsp;<strong>also</strong>&nbsp;given a&nbsp;<span style="color:#0000FF;"><strong>index&nbsp;<em>k</em></strong></span> <p><strong>For example:</strong>&nbsp;<span style="color:#FF0000;"><strong><em>k</em>&nbsp;= 2</strong></span></p> <p>&nbsp;</p> 
              <hr><p>&nbsp;</p> </li> 
             <li><strong>Problem:</strong> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> 
                  <ul> 
                   <li><span style="color:#FF0000;"><strong><em>Delete</em>&nbsp;</strong></span>the&nbsp;<strong>value&nbsp;a[k]</strong>&nbsp;from the&nbsp;<span style="color:#0000FF;"><strong>heap</strong></span>&nbsp;(so that the&nbsp;<strong>resulting tree</strong>&nbsp;is&nbsp;<span style="color:#FF0000;"><strong><em>also</em>&nbsp;a heap</strong></span>&nbsp;!!!)</li> 
                  </ul></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
         
     *  Here is a ***Heap*** with the element **a\[2\] = 5** ***deleted***:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <th>Heap&nbsp;<em>before</em>&nbsp;deleting the value&nbsp;a[2] = 5</th> 
          </tr> 
          <tr> 
           <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap05.gif"></td> 
          </tr> 
          <tr> 
           <th>Heap&nbsp;<em>after</em>&nbsp;the deletion...</th> 
          </tr> 
          <tr> 
           <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap04a.gif"></td> 
          </tr> 
         </tbody> 
        </table>
        
        **$64,000 question:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li><strong>How</strong>&nbsp;did you&nbsp;<span style="color:#FF0000;"><strong>do it</strong></span>&nbsp;??? &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
 *  **The *delete* algorithm for a *Heap***
    
     
    
     
    
    --------------------
    
    --------------------
    
    --------------------
    
    --------------------
    
     
    
     *  The **heap *deletion* algorithm** in **pseudo code**:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><span style="color:#0000FF;"><strong> 1, <span style="color:#FF0000;">Delete a node</span> from the array (this creates a "hole" and the tree is no longer "complete") 2. Replace the <span style="color:#FF0000;">deletion node</span> with the <span style="color:#FF0000;">"fartest right node"</span> on the <span style="color:#FF0000;">lowest level</span> of the Binary Tree (This step makes the tree into a "complete binary tree") 3. <span style="color:#FF0000;">Heapify</span> (fix the heap): if ( <span style="color:#FF0000;">value in replacement node &lt; its parent node</span> ) <span style="color:#FF0000;">Filter</span> the replacement node <span style="color:#FF0000;">UP</span> the binary tree else <span style="color:#FF0000;">Filter</span> the replacement node <span style="color:#FF0000;">DOWN</span> the binary tree </strong></span></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
         
     *  **Example:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li><span style="color:#FF0000;"><strong><em>Delete</em></strong></span>&nbsp;the&nbsp;<strong>node</strong>&nbsp;containing the&nbsp;<span style="color:#0000FF;"><strong>value 5</strong></span>&nbsp;from the following&nbsp;<strong>heap</strong>: <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap06.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>After you&nbsp;<strong>delete</strong>&nbsp;the node, the tree is&nbsp;<span style="color:#FF0000;"><strong>not</strong></span>&nbsp;a&nbsp;<span style="color:#0000FF;"><strong>complete binary tree</strong></span>:</p> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap07.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> 
              <hr> 
              <hr><p>&nbsp;</p> </li> 
             <li><strong>Step 1:</strong>&nbsp;<strong>replace</strong>&nbsp;the&nbsp;<span style="color:#0000FF;"><strong>deleted node</strong></span>&nbsp;with the&nbsp;<strong>node</strong>&nbsp;in the&nbsp;<span style="color:#0000FF;"><strong>"fartest right location"</strong></span>&nbsp;of the&nbsp;<span style="color:#FF0000;"><strong>lowest level</strong></span> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap08.gif"></td> 
                </tr> 
               </tbody> 
              </table><p><strong>Result:</strong></p> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap08a.gif"></td> 
                </tr> 
               </tbody> 
              </table><p><span style="color:#0000FF;"><strong>However</strong></span>, it is&nbsp;<span style="color:#FF0000;"><strong><em>not</em></strong></span>&nbsp;a&nbsp;<strong>heap</strong>:</p> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> 
                  <ul> 
                   <li>We must&nbsp;<span style="color:#0000FF;"><strong><em>fix</em></strong></span>&nbsp;the&nbsp;<strong>binary tree</strong>&nbsp;so that it becomes a&nbsp;<span style="color:#FF0000;"><strong><em>heap</em></strong></span>&nbsp;again !!! <p>&nbsp;</p> <p>&nbsp;</p> 
                    <table> 
                     <tbody> 
                      <tr> 
                       <td> 
                        <ul> 
                         <li>Depending on the&nbsp;<span style="color:#0000FF;"><strong>value</strong></span>&nbsp;of the&nbsp;<strong>replacement node</strong>, we must&nbsp;<span style="color:#FF0000;"><strong>filter</strong></span>&nbsp;the&nbsp;<strong>replacement node</strong>&nbsp;<strong>upwards</strong>&nbsp;<strong><em>or</em></strong><span style="color:#0000FF;"><strong>downwards</strong></span></li> 
                        </ul></td> 
                      </tr> 
                     </tbody> 
                    </table><p>&nbsp;</p> <p>&nbsp;</p> </li> 
                  </ul></td> 
                </tr> 
               </tbody> 
              </table><p>Since you have&nbsp;<strong><em>already</em></strong>&nbsp;seen the&nbsp;<span style="color:#FF0000;"><strong>filter&nbsp;<em>up</em></strong></span>&nbsp;algorithm --- in the&nbsp;<span style="color:#0000FF;"><strong>heap insert</strong></span>&nbsp;algorithm --- I made the&nbsp;<strong>example</strong>&nbsp;to show you the&nbsp;<span style="color:#FF0000;"><strong>filter&nbsp;<em>down</em></strong></span>&nbsp;algorithm now</p> <p>&nbsp;</p> 
              <hr><p>&nbsp;</p> </li> 
             <li><strong>Step 2:</strong>&nbsp;because the&nbsp;<strong>replacement node</strong>&nbsp;<span style="color:#FF0000;"><strong>21</strong></span>&nbsp;is&nbsp;<span style="color:#0000FF;"><strong><em>greater than</em></strong></span>&nbsp;its&nbsp;<span style="color:#FF0000;"><strong>parent node (1)</strong></span>, we must&nbsp;<span style="color:#0000FF;"><strong>filter</strong></span>&nbsp;the&nbsp;<strong>replacement node</strong>&nbsp;<span style="color:#FF0000;"><strong><em>down</em>&nbsp;the tree</strong></span> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap08x.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> <p><span style="color:#FF0000;"><strong><em>Filter</em></strong></span>&nbsp;the&nbsp;<strong><em>replacement</em>&nbsp;node</strong>&nbsp;<span style="color:#0000FF;"><strong><em>down</em></strong></span>&nbsp;the tree&nbsp;<strong>proceeds</strong>&nbsp;as&nbsp;<span style="color:#FF0000;"><strong>follows</strong></span>:</p> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> 
                  <ul> 
                   <li><strong>Compare</strong>&nbsp;the values of the&nbsp;<span style="color:#0000FF;"><strong><em>replacement</em>&nbsp;node</strong></span>&nbsp;with&nbsp;<strong>all</strong>&nbsp;its&nbsp;<span style="color:#FF0000;"><strong><em>children</em>&nbsp;nodes</strong></span>&nbsp;in the tree: <p>&nbsp;</p> 
                    <table> 
                     <tbody> 
                      <tr> 
                       <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap08b.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p>Some&nbsp;<strong>child node</strong>&nbsp;has a&nbsp;<span style="color:#0000FF;"><strong><em>smaller</em>&nbsp;value</strong></span>: the&nbsp;<strong>replacement node</strong>&nbsp;is&nbsp;<span style="color:#FF0000;"><strong><em>not</em>&nbsp;in its proper location</strong></span></p> <p>&nbsp;</p> 
                    <hr><p>&nbsp;</p> </li> 
                   <li><strong>Swap</strong>&nbsp;the&nbsp;<span style="color:#0000FF;"><strong>replacement node</strong></span>&nbsp;with the&nbsp;<span style="color:#FF0000;"><strong><em>smallest</em>&nbsp;</strong></span>of the&nbsp;<strong>children nodes</strong>: <p>&nbsp;</p> 
                    <table> 
                     <tbody> 
                      <tr> 
                       <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap08c.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p>&nbsp;</p> </li> 
                   <li><strong>After</strong>&nbsp;<span style="color:#FF0000;"><strong>swapping</strong></span>: <p>&nbsp;</p> 
                    <table> 
                     <tbody> 
                      <tr> 
                       <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap08d.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p>&nbsp;</p> <p><strong>Repeat !</strong></p> <p>&nbsp;</p> 
                    <hr> 
                    <hr><p>&nbsp;</p> </li> 
                   <li><strong>Compare</strong>&nbsp;the values of the&nbsp;<span style="color:#0000FF;"><strong><em>replacement</em>&nbsp;node (21)</strong></span>&nbsp;with&nbsp;<strong>all</strong>&nbsp;its&nbsp;<span style="color:#FF0000;"><strong><em>children</em>&nbsp;nodes</strong></span>&nbsp;in the tree: <p>&nbsp;</p> 
                    <table> 
                     <tbody> 
                      <tr> 
                       <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap08e.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p>&nbsp;</p> <p>Some&nbsp;<strong>child node</strong>&nbsp;has a&nbsp;<span style="color:#0000FF;"><strong><em>smaller</em>&nbsp;value</strong></span>: the&nbsp;<strong>replacement node</strong>&nbsp;is&nbsp;<span style="color:#FF0000;"><strong><em>not</em>&nbsp;in its proper location</strong></span></p> <p>&nbsp;</p> 
                    <hr><p>&nbsp;</p> </li> 
                   <li><strong>Swap</strong>&nbsp;the&nbsp;<span style="color:#0000FF;"><strong>replacement node</strong></span>&nbsp;with the&nbsp;<span style="color:#FF0000;"><strong><em>smallest</em>&nbsp;</strong></span>of the&nbsp;<strong>children nodes</strong>: <p>&nbsp;</p> 
                    <table> 
                     <tbody> 
                      <tr> 
                       <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap08f.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p><strong><em>After</em></strong>&nbsp;<span style="color:#FF0000;"><strong>swapping</strong></span>:</p> <p>&nbsp;</p> 
                    <table> 
                     <tbody> 
                      <tr> 
                       <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap08g.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p>&nbsp;</p> <p><strong>Repeat !</strong></p> <p>&nbsp;</p> 
                    <hr> 
                    <hr><p>&nbsp;</p> </li> 
                   <li>The&nbsp;<span style="color:#0000FF;"><strong><em>replacement</em>&nbsp;node (21)</strong></span>&nbsp;does&nbsp;<span style="color:#FF0000;"><strong>not</strong></span>&nbsp;have any&nbsp;<strong>children node</strong>: <p>&nbsp;</p> 
                    <table> 
                     <tbody> 
                      <tr> 
                       <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap08g.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p><span style="color:#FF0000;"><strong>Done</strong></span>&nbsp;!!!</p> </li> 
                  </ul></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
        --------------------
        
        --------------------
        
        --------------------
        
        --------------------
        
        --------------------
        
         
     *  **Warning:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li><strong><em>Sometimes</em></strong>, you have to&nbsp;<span style="color:#FF0000;"><strong>filter</strong></span>&nbsp;the&nbsp;<span style="color:#0000FF;"><strong>replacement node</strong></span>&nbsp;<span style="color:#FF0000;"><strong><em>up</em></strong></span>&nbsp;the Binary tree !!!!! &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
        **Example:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li><span style="color:#0000FF;"><strong>Delete</strong></span>&nbsp;the node with&nbsp;<span style="color:#FF0000;"><strong>value = 33</strong></span>&nbsp;from the following&nbsp;<strong>heap</strong>: <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap09.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> 
              <hr> 
              <hr><p>&nbsp;</p> </li> 
             <li><strong>Step 1:</strong>&nbsp;<span style="color:#0000FF;"><strong>replace</strong></span>&nbsp;the&nbsp;<strong>deleted node</strong>&nbsp;with the&nbsp;<span style="color:#FF0000;"><strong>"last" node</strong></span>&nbsp;in the&nbsp;<span style="color:#0000FF;"><strong>lowest level</strong></span>&nbsp;(to make a&nbsp;<span style="color:#FF0000;"><strong><em>complete</em>&nbsp;binary tree</strong></span>) <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap09a.gif"></td> 
                </tr> 
               </tbody> 
              </table><p><strong>Result:</strong></p> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap09b.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> 
              <hr> 
              <hr><p>&nbsp;</p> </li> 
             <li>In&nbsp;<span style="color:#0000FF;"><strong>this case</strong></span>, the&nbsp;<strong>replacement node</strong>&nbsp;must be&nbsp;<span style="color:#FF0000;"><strong>filtered&nbsp;<em>up</em></strong></span>&nbsp;into the&nbsp;<strong>binary tree</strong>: <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap09c.gif"></td> 
                </tr> 
               </tbody> 
              </table><p><strong>Result:</strong></p> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap09d.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
        --------------------
        
         
     *  **Conclusion:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><span style="color:#0000FF;"><strong> if ( <span style="color:#FF0000;">replacement node &lt; its parent node</span> ) filter the replacement node <span style="color:#FF0000;">up</span> the tree else filter the replacement node <span style="color:#FF0000;">down</span> the tree </strong></span></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
         
        
        --------------------
        
        --------------------
        
         
     *  **Heap *deletion* algorithm** in **Java**:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><span style="color:#0000FF;"><strong> public <span style="color:#FF0000;">double remove( int k )</span> { int parent; double r; // Variable to hold deleted value r = a[k]; // Save return value <span style="color:#FF0000;">a[k] = a[NNodes]</span>; // Replace deleted node with the right most leaf // This <span style="color:#FF0000;">fixes the "complete bin. tree" property</span> NNodes--; // One less node in heap.... parent = k/2; /* ======================================================= Filter a[k] up or down depending on the result of: a[k] &lt;==&gt; a[k's parent] ======================================================= */ if ( <span style="color:#FF0000;">k == 1 /* k is root */</span> || <span style="color:#FF0000;">a[parent] &lt; a[k]</span> ) HeapFilterDown(k); // Move the node a[k] DOWN the tree else HeapFilterUp(k); // Move the node a[k] UP the tree return r; // Return deleted value... } </strong></span></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
        (We have ***already*** discussed the **HeapFilterUp()** algorithm .... )
        
         
        
        --------------------
        
        --------------------
        
        --------------------
        
        --------------------
        
         
     *  **Filter Down** algorithm in **pseudo code**:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><span style="color:#0000FF;"><strong> <span style="color:#FF0000;">HeapFilterDown( k )</span> // Filter node a[k] down to its proper place { while ( a[k] has at least 1 child node ) { <span style="color:#FF0000;">child1 = 2*k;</span> // left child of a[k] <span style="color:#FF0000;">child2 = 2*k + 1;</span> // right child of a[k] if ( <span style="color:#FF0000;">a[k] has 2 childred nodes</span> ) { if ( <span style="color:#FF0000;">a[k] has smallest value</span> among {a[k], a[child1], a[child2]} ) break; // a[k] in proper place, done else { /* ========================================= Replace a[k] with the smaller child node ========================================= */ if ( a[child1] &lt; a[child2] ) { swap ( a[k], a[child1] ); k = child1; // Continue check.... } else { swap ( a[k], a[child2] ); k = child2; // Continue check... } } } else <span style="color:#FF0000;"> // a[k] must have only 1 child node</span> { if ( <span style="color:#FF0000;">a[k] has smallest value</span> among {a[k], a[child1]} ) break; // a[k] in proper place, done else { swap ( a[k], a[child1] ); k = child1; // Continue check.... } } } </strong></span></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
         
     *  The **Filter *down*** algorithm (describe above) is **coded** as a **method**:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><span style="color:#0000FF;"><strong> /* ======================================================== HeapFilterDown(k): Filters the node a[k] down the heap ======================================================== */ void HeapFilterDown( int k ) { int child1, child2; // Indices of the children nodes of k double help; while ( <span style="color:#FF0000;">2*k &lt;= NNodes</span> ) // <span style="color:#FF0000;">Does k have any child node ?</span> { <span style="color:#FF0000;">child1 = 2*k;</span> // Child1 = left child of k <span style="color:#FF0000;">child2 = 2*k+1;</span> // Child2 = right child of k if ( <span style="color:#FF0000;">child2 &lt;= NNodes</span> ) // <span style="color:#FF0000;">If true, then k has 2 children nodes !</span> { /* ======================================== Node k has 2 children nodes.... Find the min. of 3 nodes !!! ======================================== */ if ( <span style="color:#FF0000;">a[k] &lt; a[child1] &amp;&amp; a[k] &lt; a[child2]</span> ) {  /* ------------------------------------------------------- Node k has the smallest value ! Node k is in correct location... It's a heap. Stop... ------------------------------------------------------- */ <span style="color:#FF0000;">break;</span> // STOP, it's a heap now } else {  /* =================================================== Swap a[k] with the smaller of its 2 children nodes =================================================== */ if ( <span style="color:#FF0000;">a[child1] &lt; a[child2]</span> ) {  /* ------------------------------------------------------- Child1 is smaller: <span style="color:#FF0000;">swap a[k] with a[child1]</span> ------------------------------------------------------- */ help = a[k]; a[k] = a[child1]; a[child1] = help; <span style="color:#FF0000;">k = child1; </span> <span style="color:#FF0000;">// Replacement node is a[child1] // in next iteration</span> } else {  /* ------------------------------------------------------- Child2 is smaller: <span style="color:#FF0000;">swap a[k] with a[child2]</span> ------------------------------------------------------- */ help = a[k]; a[k] = a[child2]; a[child2] = help; <span style="color:#FF0000;">k = child2; </span> <span style="color:#FF0000;">// Replacement node is a[child2] // in next iteration</span> } } } else {  /* ======================================== Node k only has a left child node Find the min. of 2 nodes !!! ======================================== */ if ( <span style="color:#FF0000;">a[k] &lt; a[child1]</span> ) { /* ------------------------------------------------------- Node k is in correct location... It's a heap. Stop... ------------------------------------------------------- */ <span style="color:#FF0000;">break;</span> } else {  /* ------------------------------------------------------- Child1 is smaller: <span style="color:#FF0000;">swap a[k] with a[child1]</span> ------------------------------------------------------- */ help = a[k]; a[k] = a[child1]; a[child1] = help; <span style="color:#FF0000;">k = child1; </span> <span style="color:#FF0000;">// Replacement node is a[child1] // in next iteration</span> } } } } </strong></span></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
         
     *  **Example Program: **(Demo above code)                                                 ![Example.jpg][]
        
         
        
        **How to run the program:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li><span style="color:#0000FF;"><strong>Right click</strong></span>&nbsp;on link and&nbsp;<span style="color:#FF0000;"><strong>save</strong></span>&nbsp;in a scratch directory <p>&nbsp;</p> </li> 
             <li>To compile: &nbsp;&nbsp;<span style="color:#FF0000;"><strong>javac testProg2.java</strong></span></li> 
             <li>To run: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#FF0000;"><strong>java testProg2</strong></span></li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
         *  The **Heap class** Prog file: [click here][]
         *  The **test** Prog file: [click here][click here 1]
 *  **Running time analysis of the heap *delete* algorithm**
    
     
    
     
    
    --------------------
    
    --------------------
    
    --------------------
    
    --------------------
    
     
    
     *  **Before** we can perform a ***running time* analysis**, we must ***first*** **understand** **how** the **algorithm** works ***exactly***...
        
         
        
        --------------------
        
         
     *  **Summary** of the **heap *delete*** algorithm:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li>The&nbsp;<span style="color:#0000FF;"><strong><em>deleted</em>&nbsp;node</strong></span>&nbsp;is&nbsp;<strong><em>first</em></strong>&nbsp;replaced: <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap06.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>We will&nbsp;<strong>always</strong>&nbsp;have a&nbsp;<strong><em>complete</em>&nbsp;binary tree</strong>:</p> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap08a.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> 
              <hr><p>&nbsp;</p> </li> 
             <li><strong><em>Then</em></strong>&nbsp;the&nbsp;<span style="color:#0000FF;"><strong><em>HeapFilterUp()</em></strong></span>&nbsp;<strong><em>or</em></strong>&nbsp;the&nbsp;<span style="color:#0000FF;"><strong><em>HeapFilterDown()</em></strong></span>&nbsp;<strong>algorithm</strong>&nbsp;will&nbsp;<span style="color:#FF0000;"><strong><em>migrate</em></strong></span>&nbsp;the&nbsp;<strong>replacement node</strong>&nbsp;<span style="color:#0000FF;"><strong><em>up</em>&nbsp;or&nbsp;<em>down</em></strong></span>&nbsp;into the&nbsp;<strong>binary tree:</strong> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap08d.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>and:</p> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap08g.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
        --------------------
        
         
     *  **Fact:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li>The&nbsp;<span style="color:#0000FF;"><strong><em>number</em>&nbsp;of times</strong></span>&nbsp;that the&nbsp;<strong>deleted node</strong>&nbsp;will&nbsp;<span style="color:#FF0000;"><strong>migrate&nbsp;<em>up</em>&nbsp;or&nbsp;<em>down</em></strong></span>&nbsp;into the&nbsp;<strong>binary tree</strong>&nbsp;is: <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> <pre><span style="color:#0000FF;"><strong> <span style="color:#FF0000;"># migrations</span> ≤ <span style="color:#FF0000;">height</span> of the binary tree </strong></span></pre> </td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
        **Example:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li>The&nbsp;<span style="color:#0000FF;"><strong>maximum number</strong></span>&nbsp;of times that&nbsp;<span style="color:#FF0000;"><strong>replacement node</strong></span>&nbsp;can&nbsp;<strong>move down</strong>&nbsp;in a binary tree: <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap06a.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>is&nbsp;<span style="color:#FF0000;"><strong>at most 3 times</strong></span>:</p> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap06b.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
        The **same argument** can be apply to show that the **maximum number **of times that a **nodes** can move **up** the tree is at most the **height of the tree**.
        
         
        
        --------------------
        
        --------------------
        
         
     *  **Therefore:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><span style="color:#0000FF;"><strong> <span style="color:#FF0000;">Running time( delete(n) )</span> = Running time heap delete in heap with n node = <span style="color:#FF0000;">height</span> of a heap of n nodes </strong></span></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
         
 *  **The *height* of a heap when it contains *n* nodes**
    
     
    
     
    
    --------------------
    
    --------------------
    
    --------------------
    
    --------------------
    
     
    
     *  We have **already** determined this **fact**:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><span style="color:#0000FF;"><strong> Let: n = # nodes in heap of height h 2h - 1 &lt; n ≤ 2h+1 − 1 &lt;===&gt; 2h &lt; n + 1 ≤ 2h+1 &lt;===&gt; h &lt; lg(n + 1) ≤ h+1 ===&gt; <span style="color:#FF0000;">height</span> of heap ~= <span style="color:#FF0000;">lg(n + 1)</span> </strong></span></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
         
 *  **Running time of the heap *delete* algorithm**
    
     
    
     *  **Summary:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li><span style="color:#FF0000;"><strong><em>Running time</em></strong></span>&nbsp;of&nbsp;<strong>delete</strong>&nbsp;into a&nbsp;<span style="color:#0000FF;"><strong>heap</strong></span>&nbsp;of&nbsp;<span style="color:#FF0000;"><strong><em>n</em>&nbsp;nodes</strong></span>&nbsp;=&nbsp;<span style="color:#FF0000;"><strong><em>height</em></strong></span>&nbsp;of the&nbsp;<span style="color:#0000FF;"><strong>heap</strong></span> <p>&nbsp;</p> 
              <hr><p>&nbsp;</p> </li> 
             <li><span style="color:#FF0000;"><strong><em>height</em></strong></span>&nbsp;of the&nbsp;<span style="color:#0000FF;"><strong>heap</strong></span>&nbsp;containing&nbsp;<strong><em>n</em>&nbsp;nodes</strong>&nbsp;~=&nbsp;<span style="color:#FF0000;"><strong><em>lg(n + 1)</em></strong></span></li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
         
     *  **Conclusion:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li><span style="color:#FF0000;"><strong><em>Running time</em></strong></span>&nbsp;of&nbsp;<strong>delete</strong>&nbsp;into a&nbsp;<span style="color:#0000FF;"><strong>heap</strong></span>&nbsp;of&nbsp;<span style="color:#FF0000;"><strong><em>n</em>&nbsp;nodes</strong></span>&nbsp;=&nbsp;<strong><em>O(lg(n))</em></strong>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>

[http_www.mathcs.emory.edu_cheung_Courses_171_Syllabus_9-BinTree_heap-delete.html]: http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/heap-delete.html
[Example.jpg]: /images/20220411/6b04edfb89344f0c8d86798a72ab2d75.png
[click here]: http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/Progs/Heap/Basic/delete/Heap.java
[click here 1]: http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/Progs/Heap/Basic/delete/testProg2.java