图解-堆插入节点

电玩女神 2022-04-11 04:12 200阅读 0赞

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

*  ***Inserting* a value into 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/Heap03.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>value&nbsp;<em>x</em></strong></span> <p><strong>For example:</strong>&nbsp;<span style="color:#ff0000;"><strong><em>x</em>&nbsp;= 3</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>Insert</em>&nbsp;</strong></span>the&nbsp;<strong>value&nbsp;<em>x</em></strong>&nbsp;into 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*** containing the ***inserted* value 3**:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <th>Heap&nbsp;<em>before</em>&nbsp;inserting the value 3</th> 
          </tr> 
          <tr> 
           <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap03.gif"></td> 
          </tr> 
          <tr> 
           <th>Heap&nbsp;<em>after</em>&nbsp;inserting the value 3</th> 
          </tr> 
          <tr> 
           <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap03g.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 *insert* algorithm for a *Heap***
    
     
    
     
    
    --------------------
    
    --------------------
    
    --------------------
    
    --------------------
    
     
    
     *  The **heap *insertion* algorithm** in **pseudo code**:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><code>    Insert a node containing the insertion value
               in the "fartest left location" of the lowest level
               of the Binary Tree
        
            Filter the inserted node up using this algorithm:
        
               while (  inserted node's value &lt; value in its parent node )     
               {
                  swap the values of the respective node;
               }
        </code></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
         
     *  **Example:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li><span style="color:#ff0000;"><strong><em>Insert</em></strong></span>&nbsp;the&nbsp;<span style="color:#0000ff;"><strong>value 3</strong></span>&nbsp;into 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/Heap03.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>Insert a node</strong></span>&nbsp;containing the&nbsp;<span style="color:#ff0000;"><strong>insertion value (= 3)</strong></span>&nbsp;in the&nbsp;<span style="color:#0000ff;"><strong>"fartest left 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/Heap03a.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> 
              <hr><p>&nbsp;</p> </li> 
             <li><strong>Step 2:</strong>&nbsp;<span style="color:#ff0000;"><strong><em>Filter</em></strong></span>&nbsp;the&nbsp;<strong>inserted node</strong>&nbsp;<span style="color:#0000ff;"><strong><em>up</em></strong></span>&nbsp;the tree <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> 
                  <ul> 
                   <li><strong>Compare</strong>&nbsp;the values of the&nbsp;<span style="color:#0000ff;"><strong><em>inserted</em>&nbsp;node</strong></span>&nbsp;with its&nbsp;<span style="color:#ff0000;"><strong><em>parent</em>&nbsp;node</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/Heap03b.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p>&nbsp;</p> 
                    <hr><p>&nbsp;</p> </li> 
                   <li><span style="color:#0000ff;"><strong>3</strong></span>&nbsp;is&nbsp;<span style="color:#ff0000;"><strong><em>smaller</em></strong></span>&nbsp;than its&nbsp;<span style="color:#0000ff;"><strong><em>parent</em>&nbsp;value (11)</strong></span>:&nbsp;<span style="color:#ff0000;"><strong>swap</strong></span>&nbsp;!!! <p>&nbsp;</p> 
                    <table> 
                     <tbody> 
                      <tr> 
                       <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap03c.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><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>inserted</em>&nbsp;node</strong></span>&nbsp;with its&nbsp;<span style="color:#ff0000;"><strong><em>parent</em>&nbsp;node</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/Heap03d.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p>&nbsp;</p> 
                    <hr><p>&nbsp;</p> </li> 
                   <li><span style="color:#0000ff;"><strong>3</strong></span>&nbsp;is&nbsp;<span style="color:#ff0000;"><strong><em>smaller</em></strong></span>&nbsp;than its&nbsp;<span style="color:#0000ff;"><strong><em>parent</em>&nbsp;value (5)</strong></span>:&nbsp;<span style="color:#ff0000;"><strong>swap</strong></span>&nbsp;!!! <p>&nbsp;</p> 
                    <table> 
                     <tbody> 
                      <tr> 
                       <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap03e.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><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>inserted</em>&nbsp;node</strong></span>&nbsp;with its&nbsp;<span style="color:#ff0000;"><strong><em>parent</em>&nbsp;node</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/Heap03f.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p>&nbsp;</p> 
                    <hr><p>&nbsp;</p> </li> 
                   <li>The&nbsp;<span style="color:#0000ff;"><strong><em>parent</em>&nbsp;node</strong></span>&nbsp;has a&nbsp;<span style="color:#ff0000;"><strong><em>smaller</em>&nbsp;value</strong></span>, so&nbsp;<span style="color:#0000ff;"><strong>3</strong></span>&nbsp;is in its&nbsp;<span style="color:#ff0000;"><strong><em>correct</em>&nbsp;place</strong></span>&nbsp;!!! <p>We are&nbsp;<strong>done</strong>.</p> <p>The result is a&nbsp;<span style="color:#ff0000;"><strong>good&nbsp;<em>heap</em></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/Heap03g.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p>&nbsp;</p> </li> 
                  </ul></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
        --------------------
        
         
     *  **Heap *insertion* algorithm** in **Java**:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><code>   void put( double x )
           {
              a[NNodes+1] = x;           // Insert x in the "fartest left location"    
                                         // This preserves the "complete bin tree" prop
        
              NNodes++;                  // We have 1 more node
        
              HeapFilterUp( NNodes );    // Filter the inserted node 
        
                                         // The FilterUp() method need to know
        				 // which node is the inserted node !!!
        				 // The parameter NNodes identifies the
        				 // inserted node a[NNodes]
           }
        </code></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
         
     *  The **Filter Up** algorithm in **pseudo code**:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><code>   HeapFilterUp( k )    // Filter up the node a[k]
           {
              while ( k has a parent node )
              {
                 parent = k/2;     // a[parent] is the parent node of a[k]
        
                 if ( a[k] &lt; a[parent] )
        	 {
        	    swap a[k] &lt;--&gt; a[parent];
        
        	    k = parent;
                 }
        	 else
        	 {
        	    break;          // a[k] is in correct position, DONE !     
        	 }
              }
        </code></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
         
     *  The **Filter up** algorithm (describe above) is **coded** as a **method**:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><code>   /* ===================================================
              HeapFilterUp(k): Filters the node a[k] up the heap
              =================================================== */
           void HeapFilterUp( int k )
           {
              int parent;                 // parent = parent node of k
              double help;		  // Used for swapping
        
              while ( parent &gt; 0 )        // parent == 0 means no parent
              {
                 parent = k/2;            // Find parent node of k
        
                 if ( a[k] &lt; a[parent] )
                 {
                    /* =====================================
        	       Wrong order: swap a[k] and a[parent]
        	       ===================================== */
                    help = a[parent];
                    a[parent] = a[k];
                    a[k] = help;
        
        	    /* ------------------------------
        	       Continue one level in the tree
        	       ------------------------------ */
                    k = parent;
                 }
                 else
                 {
                    break;            // k is in correct position - DONE !     
                 }
        
              }
           }
        </code></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 testProg.java</strong></span></li> 
             <li>To run: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<span style="color:#ff0000;"><strong>java testProg</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 *insert* algorithm**
    
     
    
     
    
    --------------------
    
    --------------------
    
    --------------------
    
    --------------------
    
     
    
     *  **Before** we can perform a ***running time* analysis**, we must ***first*** **understand** **how** the **algorithm** works ***exactly***...
        
         
        
        --------------------
        
         
     *  **Summary** of the **heap *insert*** algorithm:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li>The&nbsp;<span style="color:#0000ff;"><strong>node</strong></span>&nbsp;is&nbsp;<strong><em>always</em></strong>&nbsp;inserted as the&nbsp;<span style="color:#ff0000;"><strong><em>left</em>&nbsp;most leaf node</strong></span>: <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap03a.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> 
              <hr><p>&nbsp;</p> </li> 
             <li>The the&nbsp;<span style="color:#0000ff;"><strong><em>HeapFilterUp()</em></strong></span>&nbsp;<strong>algorithm</strong>&nbsp;will&nbsp;<span style="color:#ff0000;"><strong><em>migrate</em></strong></span>&nbsp;the&nbsp;<strong>insert node</strong>&nbsp;<span style="color:#0000ff;"><strong><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/Heap03c.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/Heap03g.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>inserted node</strong>&nbsp;will&nbsp;<span style="color:#ff0000;"><strong>migrate up</strong></span>&nbsp;into the&nbsp;<strong>binary tree</strong>&nbsp;is: <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> <pre><code>    # migrations ≤ height of the binary tree               
        </code></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 this that&nbsp;<span style="color:#ff0000;"><strong>node 3</strong></span>&nbsp;can&nbsp;<strong>move up</strong>&nbsp;in this binary tree: <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap03a.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/Heap03h.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
        --------------------
        
         
     *  **Therefore:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><code>   Running time( insert(n) ) = Running time heap insert in heap with n node     
        
                                     = height of a heap of n nodes   
        </code></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
         
 *  **The *height* of a heap when it contains *n* nodes**
    
     
    
     
    
    --------------------
    
    --------------------
    
    --------------------
    
    --------------------
    
     
    
     *  **Recall:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li>A&nbsp;<span style="color:#0000ff;"><strong><em>perfect</em>&nbsp;binary tree</strong></span>&nbsp;of&nbsp;<span style="color:#ff0000;"><strong>height&nbsp;<em>h</em></strong></span>&nbsp;has: <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> 
                  <ul> 
                   <li><span style="color:#ff0000;"><strong><em>2h+1&nbsp;− 1</em></strong></span>&nbsp;nodes &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <p>(See:&nbsp;<a href="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/bin-tree.html#prop2" rel="nofollow"><span style="color:#0000ff;"><strong>click here</strong></span>&nbsp;</a>)</p> </li> 
                  </ul></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
             <li><strong><em>Similarly</em></strong>, a&nbsp;<span style="color:#0000ff;"><strong><em>perfect</em>&nbsp;binary tree</strong></span>&nbsp;of&nbsp;<span style="color:#ff0000;"><strong>height&nbsp;<em>h−1</em></strong></span>&nbsp;has: <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> 
                  <ul> 
                   <li><span style="color:#ff0000;"><strong><em>2h&nbsp;− 1</em></strong></span>&nbsp;nodes &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <p>(See:&nbsp;<a href="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/bin-tree.html#prop2" rel="nofollow"><span style="color:#0000ff;"><strong>click here</strong></span>&nbsp;</a>)</p> </li> 
                  </ul></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
         
     *  **Fact:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li>(A&nbsp;<span style="color:#ff0000;"><strong><em>heap</em></strong></span>&nbsp;is a&nbsp;<span style="color:#0000ff;"><strong><em>complete</em>&nbsp;binary tree</strong></span>) <p>The&nbsp;<span style="color:#0000ff;"><strong>number of nodes&nbsp;<em>n</em></strong></span>&nbsp;in a&nbsp;<span style="color:#ff0000;"><strong><em>complete</em>&nbsp;binary tree</strong></span>&nbsp;(i.e., a heap) of&nbsp;<span style="color:#0000ff;"><strong>height&nbsp;<em>h</em></strong></span>&nbsp;is between:</p> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> <pre><code>   2h − 1 &lt; n ≤ 2h+1 − 1         
        </code></pre> </td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
        **Proof:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li>A&nbsp;<span style="color:#0000ff;"><strong><em>complete</em>&nbsp;binary tree</strong></span>&nbsp;of&nbsp;<span style="color:#ff0000;"><strong>height&nbsp;<em>h</em></strong></span>: <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/Heap03i.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>will have&nbsp;<strong><em>more</em>&nbsp;nodes</strong>&nbsp;than a&nbsp;<span style="color:#0000ff;"><strong><em>perfect</em>&nbsp;binary tree</strong></span>&nbsp;of&nbsp;<span style="color:#ff0000;"><strong>height&nbsp;<em>h−1</em></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/Heap03j.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>and it will have&nbsp;<strong><em>at most</em>&nbsp;as many nodes</strong>&nbsp;as a&nbsp;<span style="color:#0000ff;"><strong><em>perfect</em>&nbsp;binary tree</strong></span>&nbsp;of&nbsp;<span style="color:#ff0000;"><strong>height&nbsp;<em>h</em></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/Heap03k.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
        **Therefore:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><code>  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; height of heap ~= lg(n + 1)         
        </code></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
         
 *  **Running time of the heap *insert* algorithm**
    
     
    
     *  **Summary:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li><span style="color:#ff0000;"><strong><em>Running time</em></strong></span>&nbsp;of&nbsp;<strong>insert</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>insert</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;&nbsp;&nbsp;&nbsp;</li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>

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