图解-堆排序 in-place Heap Sort

川长思鸟来 2022-04-11 04:13 159阅读 0赞

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

*  **Short-coming of the previous "simple" Heap Sort algorithm**
    
     
    
     *  **Consider** the (previously discussed) ***simple* Heap Sort algorithm**:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><span style="color:#0000FF;"><strong> public static void main(String[] args) { Scanner in = new Scanner(System.in); double a[] = {9.2, 4.2, 1.1, 6.4, 3.5, 8.9, 2.5, 7.5}; <span style="color:#FF0000;">// Array 1</span> Heap x = <span style="color:#FF0000;">new Heap( 100 );</span> <span style="color:#FF0000;">// Array 2</span> for ( int i = 0; i &lt; a.length; i++ ) { System.out.println("Insert: " + a[i] ); <span style="color:#FF0000;">x.put( a[i] );</span> x.printHeap(); } System.out.println("\n\nKeep removing the first node : "); for ( int i = 0; i &lt; a.length; i++ ) { double r; r = x.remove(1); System.out.print( r + ", "); } System.out.println(); } </strong></span></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
        This **algorithm** uses ***2 (two)* arrays**:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li>The array&nbsp;<strong>a[ ]</strong>&nbsp;to store the&nbsp;<strong>data</strong>&nbsp;that we want to&nbsp;<span style="color:#0000FF;"><strong>sort</strong></span> <p>&nbsp;</p> 
              <hr><p>&nbsp;</p> </li> 
             <li>The&nbsp;<span style="color:#FF0000;"><strong><em>Heap</em></strong></span>&nbsp;data structure (that we&nbsp;<span style="color:#0000FF;"><strong>create</strong></span>&nbsp;with the&nbsp;<span style="color:#FF0000;"><strong>new Heap(100)</strong></span>)&nbsp;<strong><em>also</em></strong>&nbsp;uses an&nbsp;<strong>array</strong>&nbsp;!!!</li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
        --------------------
        
         
     *  **Idea:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li>Can we use the&nbsp;<strong><em>input</em>&nbsp;array</strong>&nbsp;<strong>a[ ]</strong>&nbsp;as a&nbsp;<span style="color:#FF0000;"><strong>Heap</strong></span>&nbsp;??? <p>In other words:</p> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> 
                  <ul> 
                   <li>Can we&nbsp;<span style="color:#0000FF;"><strong><em>apply</em></strong></span>&nbsp;the&nbsp;<span style="color:#FF0000;"><strong>heap&nbsp;<em>insert</em>/<em>delete</em>&nbsp;algorithm</strong></span>&nbsp;<strong><em>directly</em></strong>&nbsp;on the&nbsp;<strong>array</strong>&nbsp;<strong>a[ ]</strong>&nbsp;???</li> 
                  </ul></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
    
     
    
    --------------------
    
    --------------------
    
    --------------------
    
    --------------------
    
     
 *  **Input data assumption**
    
     
    
     *  **Facts:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li>The&nbsp;<strong><em>input</em>&nbsp;data</strong>&nbsp;that will be&nbsp;<span style="color:#0000FF;"><strong><em>sorted</em></strong></span>&nbsp;are&nbsp;<strong><em>normally</em></strong>&nbsp;stored in an&nbsp;<strong>array</strong>&nbsp;that&nbsp;<span style="color:#FF0000;"><strong><em>starts</em></strong></span>&nbsp;with the&nbsp;<span style="color:#0000FF;"><strong>index 0</strong></span>&nbsp;in&nbsp;<strong>Java</strong> <p>&nbsp;</p> 
              <hr><p>&nbsp;</p> </li> 
             <li><span style="color:#FF0000;"><strong>However</strong></span>: <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> 
                  <ul> 
                   <li>When we&nbsp;<strong>use</strong>&nbsp;an&nbsp;<span style="color:#0000FF;"><strong><em>array</em></strong></span>&nbsp;to&nbsp;<span style="color:#FF0000;"><strong>represent</strong></span>&nbsp;a&nbsp;<strong>Heap</strong>, we&nbsp;<span style="color:#0000FF;"><strong>leave</strong></span>&nbsp;the array element&nbsp;<span style="color:#FF0000;"><strong>a[0]</strong></span>&nbsp;<strong><em>unused</em>&nbsp;(empty)</strong>...</li> 
                  </ul></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
         
     *  We **adopt** the following **assumption** on the ***input* data** (that we want to **sort**) in the **Heap Sort** algorithm:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li>The&nbsp;<strong><em>input</em>&nbsp;data</strong>&nbsp;that will be&nbsp;<span style="color:#0000FF;"><strong><em>sorted</em></strong></span>&nbsp;are stored in an&nbsp;<strong>array</strong>&nbsp;that&nbsp;<span style="color:#FF0000;"><strong><em>starts</em></strong></span>&nbsp;with the&nbsp;<span style="color:#0000FF;"><strong>index 1</strong></span>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <p>(I.e., the array element&nbsp;<span style="color:#FF0000;"><strong>a[0]</strong></span>&nbsp;is&nbsp;<span style="color:#0000FF;"><strong><em>not</em>&nbsp;used</strong></span>)</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
        **Example:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li>If we want to&nbsp;<span style="color:#0000FF;"><strong>sort</strong></span>&nbsp;the&nbsp;<strong>values</strong>: <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> <pre><span style="color:#0000FF;"><strong> 9.2, 4.2, 1.1, 6.4, 3.5, 8.9, 2.5, 7.5 </strong></span></pre> </td> 
                </tr> 
               </tbody> 
              </table><p>we will use an&nbsp;<strong>array</strong>&nbsp;with a&nbsp;<span style="color:#FF0000;"><strong><em>dummy</em>&nbsp;value</strong></span>&nbsp;in&nbsp;<span style="color:#0000FF;"><strong>a[0]</strong></span>:</p> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> <pre><span style="color:#0000FF;"><strong> double[] a = { <span style="color:#FF0000;">0.0</span>, 9.2, 4.2, 1.1, 6.4, 3.5, 8.9, 2.5, 7.5}; </strong></span></pre> </td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
    
     
    
    --------------------
    
    --------------------
    
    --------------------
    
    --------------------
    
     
 *  ***Overview* of the *in-place* Heap Sort algorithm**
    
     
    
     *  The ***in-place*** Heap Sort algorithm consists of **2 phases**:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ol> 
             <li><span style="color:#FF0000;"><strong>Heap building (<em>insert</em>)</strong></span>&nbsp;phase: <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> 
                  <ul> 
                   <li>In this phase, the&nbsp;<span style="color:#0000FF;"><strong><em>input</em>&nbsp;array</strong></span>&nbsp;is&nbsp;<strong>slowly</strong>&nbsp;transformed into a&nbsp;<span style="color:#FF0000;"><strong>Heap</strong></span>&nbsp;--- one&nbsp;<strong>array element</strong>&nbsp;at a time.</li> 
                  </ul></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> 
              <hr><p>&nbsp;</p> </li> 
             <li><span style="color:#FF0000;"><strong>Heap teardown (<em>delete</em>)</strong></span>&nbsp;phase: <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> 
                  <ul> 
                   <li>In this phase, the&nbsp;<span style="color:#0000FF;"><strong><em>root</em>&nbsp;node</strong></span>&nbsp;of the&nbsp;<strong>Heap</strong>&nbsp;is&nbsp;<span style="color:#FF0000;"><strong><em>moved</em></strong></span>&nbsp;to the&nbsp;<span style="color:#0000FF;"><strong><em>back</em></strong></span>&nbsp;of the&nbsp;<strong>array</strong>&nbsp;and the&nbsp;<strong>heap</strong>&nbsp;is&nbsp;<span style="color:#0000FF;"><strong>torn down</strong></span>, one&nbsp;<strong>array element</strong>&nbsp;at a time.</li> 
                  </ul></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ol></td> 
          </tr> 
         </tbody> 
        </table>
        
         
    
     
    
    --------------------
    
    --------------------
    
    --------------------
    
    --------------------
    
     
 *  **Heap Sort Phase 1: building an *in-place* heap**
    
     
    
     *  I will **illustrate** the **Phase 1 algorithm** with an **example**:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><span style="color:#0000FF;"><strong> Input array: a = { <span style="color:#FF0000;">0.0</span>, 9.2, 4.2, 1.1, 6.4, 3.5, 8.9, 2.5, 7.5}; </strong></span></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
         
     *  We ***pretend*** that the ***input* array** is **partitioned** into **2 segments**:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li>A&nbsp;<span style="color:#0000FF;"><strong><em>heap</em>&nbsp;segment</strong></span>&nbsp;consisting of the&nbsp;<span style="color:#FF0000;"><strong>array elements</strong></span>: <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> <pre><span style="color:#0000FF;"><strong> a[1] a[2] .... a[k] </strong></span></pre> </td> 
                </tr> 
               </tbody> 
              </table><p>that&nbsp;<strong>form</strong>&nbsp;a&nbsp;<span style="color:#FF0000;"><strong><em>Heap</em></strong></span></p> <p>&nbsp;</p> 
              <hr><p>&nbsp;</p> </li> 
             <li>A&nbsp;<span style="color:#FF0000;"><strong><em>unprocessed</em>&nbsp;segment</strong></span>&nbsp;of&nbsp;<span style="color:#0000FF;"><strong><em>unprocessed</em>&nbsp;array elements</strong></span>: <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> <pre><span style="color:#0000FF;"><strong> a[k+1] a[k+2] .... a[N] </strong></span></pre> </td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
         
     *  ***Initially***, the ***heap* segments** consists of ***only*** one array element (**a\[0\]**):
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/HeapSort01.gif"></td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
        --------------------
        
         
     *  I will now do a **few** ***iterations*** of the **Phase 1 algorithm**:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li><strong>Iteration 1:</strong> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> 
                  <ul> 
                   <li><strong>Step 1:</strong>&nbsp;<span style="color:#0000FF;"><strong>add</strong></span>&nbsp;the&nbsp;<span style="color:#FF0000;"><strong>next array element (a[2] = 4.2)</strong></span>&nbsp;to the&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/HeapSort02.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p>&nbsp;</p> 
                    <hr><p>&nbsp;</p> </li> 
                   <li><strong>Step 2:</strong>&nbsp;<span style="color:#0000FF;"><strong><em>Filter</em>&nbsp;</strong></span>the&nbsp;<span style="color:#FF0000;"><strong><em>newly added</em>&nbsp;next array element (a[2] = 4.2)</strong></span>&nbsp;<span style="color:#0000FF;"><strong>up</strong></span>&nbsp;into the&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/HeapSort03.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p>&nbsp;</p> </li> 
                  </ul></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> 
              <hr> 
              <hr><p>&nbsp;</p> </li> 
             <li><strong>Iteration 2:</strong> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> 
                  <ul> 
                   <li><strong>Step 1:</strong>&nbsp;<span style="color:#0000FF;"><strong>add</strong></span>&nbsp;the&nbsp;<span style="color:#FF0000;"><strong>next array element (a[3] = 1.1)</strong></span>&nbsp;to the&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/HeapSort04.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p>&nbsp;</p> 
                    <hr><p>&nbsp;</p> </li> 
                   <li><strong>Step 2:</strong>&nbsp;<span style="color:#0000FF;"><strong><em>Filter</em>&nbsp;</strong></span>the&nbsp;<span style="color:#FF0000;"><strong><em>newly added</em>&nbsp;next array element (a[3] = 1.1)</strong></span>&nbsp;<span style="color:#0000FF;"><strong>up</strong></span>&nbsp;into the&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/HeapSort05.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p>&nbsp;</p> </li> 
                  </ul></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> 
              <hr> 
              <hr><p>&nbsp;</p> </li> 
             <li>One more and I will stop,&nbsp;<strong>Iteration 3:</strong> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> 
                  <ul> 
                   <li><strong>Step 1:</strong>&nbsp;<span style="color:#0000FF;"><strong>add</strong></span>&nbsp;the&nbsp;<span style="color:#FF0000;"><strong>next array element (a[4] = 6.4)</strong></span>&nbsp;to the&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/HeapSort06.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p>&nbsp;</p> 
                    <hr><p>&nbsp;</p> </li> 
                   <li><strong>Step 2:</strong>&nbsp;<span style="color:#0000FF;"><strong><em>Filter</em>&nbsp;</strong></span>the&nbsp;<span style="color:#FF0000;"><strong><em>newly added</em>&nbsp;next array element (a[4] = 6.4)</strong></span>&nbsp;<span style="color:#0000FF;"><strong>up</strong></span>&nbsp;into the&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/HeapSort07.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p>&nbsp;</p> </li> 
                  </ul></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
        --------------------
        
        --------------------
        
         
        
         
     *  The ***Phase 1* **of the **Heap Sort** algorithm:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><span style="color:#0000FF;"><strong> // Initially: heap segment = {a[1]} for ( every element x = a[2], a[3], a[4], .... ) { "Include x into the Heap;" // We don't need to do anything !!! // We just pretend the heap segment // has expanded by 1 array element <span style="color:#FF0000;">filter x up the heap;</span> } </strong></span></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
        --------------------
        
         
     *  The ***Phase 1* algorithm** in **Java**:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><span style="color:#0000FF;"><strong> NNodes = 1; // Start the Heap with a[1] for (i = 2; i &lt; a.length; i++) { <span style="color:#FF0000;"><strong>NNodes++;</strong></span><strong> // "Include" the next node <span style="color:#FF0000;">HeapFilterUp(a, NNodes);</span> // Filter a[NNodes] up the heap. } </strong></strong></span></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
         
    
     
    
    --------------------
    
    --------------------
    
    --------------------
    
    --------------------
    
     
 *  **The result of the *Phase 1* algorithm**
    
     
    
     *  **Fact:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li>When&nbsp;<span style="color:#0000FF;"><strong><em>Phase 1</em></strong></span>&nbsp;of the&nbsp;<strong>Heap Sort</strong>&nbsp;algorithm&nbsp;<span style="color:#FF0000;"><strong>completes</strong></span>, the&nbsp;<span style="color:#0000FF;"><strong><em>input</em>&nbsp;array (a[ ])</strong></span>&nbsp;will be&nbsp;<strong>transformed</strong>&nbsp;into a&nbsp;<span style="color:#FF0000;"><strong><em>Heap</em></strong></span></li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
         
     *  **Example:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li>Initial&nbsp;<span style="color:#0000FF;"><strong><em>input</em>&nbsp;array</strong></span>: <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/HeapSort01.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> 
              <hr><p>&nbsp;</p> </li> 
             <li>When&nbsp;<span style="color:#0000FF;"><strong>phase 1</strong></span>&nbsp;completes, the&nbsp;<span style="color:#FF0000;"><strong>input array</strong></span>&nbsp;will be a&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/HeapSort08.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
    
     
    
    --------------------
    
    --------------------
    
    --------------------
    
    --------------------
    
     
    
    --------------------
    
    --------------------
    
    --------------------
    
    --------------------
    
     
 *  **Heap Sort Pase 2: tearing down the *in-place* heap**
    
     
    
     *  In **Phase 2**, we ***repeatedly* remove** the **root node** of the (in-place) **heap**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li>The&nbsp;<span style="color:#0000FF;"><strong><em>root</em>&nbsp;node</strong></span>&nbsp;of the&nbsp;<strong>Heap</strong>&nbsp;is (always) stored in the&nbsp;<span style="color:#FF0000;"><strong>array element&nbsp;a[1]</strong></span> <p><strong>Example:</strong></p> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><strong><strong><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/HeapSort09.gif"></strong></strong></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
         
     *  **Recall:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li>When we&nbsp;<span style="color:#0000FF;"><strong>delete</strong></span>&nbsp;a&nbsp;<span style="color:#FF0000;"><strong>node</strong></span>&nbsp;from the&nbsp;<strong>Heap</strong>, we must&nbsp;<span style="color:#0000FF;"><strong>first</strong></span>: <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> 
                  <ul> 
                   <li><span style="color:#FF0000;"><strong><em>Replace</em></strong></span>&nbsp;the&nbsp;<strong>deleted node</strong>&nbsp;with the&nbsp;<span style="color:#0000FF;"><strong><em>right-most</em>&nbsp;leaf node</strong></span>&nbsp;in the&nbsp;<span style="color:#FF0000;"><strong><em>lowest</em>&nbsp;level</strong></span></li> 
                  </ul></td> 
                </tr> 
               </tbody> 
              </table><p><strong>Example:</strong></p> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> 
                  <ul> 
                   <li><strong><strong>When we&nbsp;<span style="color:#0000FF;"><strong>delete</strong></span>&nbsp;the&nbsp;<span style="color:#FF0000;"><strong>root node 1.1</strong></span>:</strong></strong> <p>&nbsp;</p> 
                    <table> 
                     <tbody> 
                      <tr> 
                       <td><strong><strong><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/HeapSort10.gif"></strong></strong></td> 
                      </tr> 
                     </tbody> 
                    </table><p>&nbsp;</p> 
                    <hr><p>&nbsp;</p> </li> 
                   <li><strong><strong>We&nbsp;<strong>first</strong>&nbsp;replace the&nbsp;<span style="color:#0000FF;"><strong>root node</strong></span>&nbsp;with the&nbsp;<span style="color:#FF0000;"><strong>node 6.4</strong></span>:</strong></strong> <p>&nbsp;</p> 
                    <table> 
                     <tbody> 
                      <tr> 
                       <td><strong><strong><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/HeapSort11.gif"></strong></strong></td> 
                      </tr> 
                     </tbody> 
                    </table><p>&nbsp;</p> </li> 
                  </ul></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
        --------------------
        
         
     *  The **Heap *deletion* algorithm** will then use the **filter *down*** algorithm to transform the **tree** into a **Heap**
        
        (Remember that in a **Heap**, the ***root* node** of ***each* subtree** must have the ***smallest* value** in its **subtree** -
        
        The **filter *down*** algorithm will **fix** the **tree** to **comply** with this **property**)
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li>We can (and will)&nbsp;<span style="color:#0000FF;"><strong>apply</strong></span>&nbsp;the&nbsp;<span style="color:#FF0000;"><strong>filter&nbsp;<em>down</em></strong></span>&nbsp;algorithm to&nbsp;<strong>fix</strong>&nbsp;the&nbsp;<span style="color:#0000FF;"><strong>tree</strong></span>... <p>(We will discuss that later...)</p> <p><span style="color:#FF0000;"><strong>But&nbsp;<em>more importantly</em></strong></span>, notice that:</p> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/HeapSort11.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>The&nbsp;<span style="color:#0000FF;"><strong>array</strong></span>&nbsp;has a&nbsp;<span style="color:#FF0000;"><strong><em>empty</em>&nbsp;slot</strong></span>&nbsp;at the&nbsp;<span style="color:#0000FF;"><strong>end</strong></span>&nbsp;!!!</p> <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> 
                  <ul> 
                   <li>We can&nbsp;<strong>use</strong>&nbsp;this&nbsp;<span style="color:#0000FF;"><strong><em>empty</em>&nbsp;slot</strong></span>&nbsp;to&nbsp;<strong>store</strong>&nbsp;the&nbsp;<span style="color:#FF0000;"><strong><em>deleted</em>&nbsp;value (1.1)</strong></span>&nbsp;!!! <p>(This&nbsp;<strong>trick</strong>&nbsp;makes the&nbsp;<strong>Heap Sort</strong>&nbsp;algorithm an&nbsp;<span style="color:#FF0000;"><strong><em>in-place</em>&nbsp;algorithm</strong></span>&nbsp;--- we don't need another array !!!)</p> </li> 
                  </ul></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
         
        
        --------------------
        
        --------------------
        
        --------------------
        
         
     *  This is what I mean:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li>We&nbsp;<strong>store</strong>&nbsp;the&nbsp;<span style="color:#FF0000;"><strong>deleted value</strong></span>&nbsp;into the&nbsp;<span style="color:#0000FF;"><strong><em>empty</em>&nbsp;slot</strong></span>&nbsp;created by the&nbsp;<span style="color:#FF0000;"><strong><em>replacement</em>&nbsp;step</strong></span>&nbsp;of the&nbsp;<span style="color:#0000FF;"><strong>Heap deletion algorithm</strong></span>: <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/HeapSort12.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
        --------------------
        
         
     *  Now we perform the **filter *down*** algorithm to **fix** the **Heap**:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li>Initially: <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/HeapSort13.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> 
              <hr><p>&nbsp;</p> </li> 
             <li><span style="color:#FF0000;"><strong>Filter down</strong></span>:&nbsp;<span style="color:#0000FF;"><strong>swap</strong></span>&nbsp;with the&nbsp;<span style="color:#FF0000;"><strong><em>smallest</em>&nbsp;child 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/HeapSort13a.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/HeapSort13b.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> 
              <hr> 
              <hr><p>&nbsp;</p> </li> 
             <li>Since&nbsp;<span style="color:#FF0000;"><strong>6.4</strong></span>&nbsp;is&nbsp;<span style="color:#0000FF;"><strong><em>smaller</em></strong></span>&nbsp;than its&nbsp;<span style="color:#FF0000;"><strong><em>children nodes</em>&nbsp;(9.2 and 7.5)</strong></span>, we have a&nbsp;<strong>Heap</strong>&nbsp;again.</li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
        --------------------
        
         
     *  I will now do ***one* more** **iteration** of the **Phase 2** algorithm (starting with the last result):
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li><strong>Iteration 2:</strong>&nbsp;(the previous iteration was the first iteration !) <p>&nbsp;</p> 
              <table> 
               <tbody> 
                <tr> 
                 <td> 
                  <ul> 
                   <li><strong>Initially:</strong> <p>&nbsp;</p> 
                    <table> 
                     <tbody> 
                      <tr> 
                       <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/HeapSort14.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p>&nbsp;</p> 
                    <hr><p>&nbsp;</p> </li> 
                   <li><span style="color:#0000FF;"><strong>Delete</strong></span>&nbsp;the&nbsp;<span style="color:#FF0000;"><strong><em>root</em>&nbsp;node (a[1])</strong></span>: <p>&nbsp;</p> 
                    <table> 
                     <tbody> 
                      <tr> 
                       <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/HeapSort14a.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p>(We&nbsp;<span style="color:#0000FF;"><strong>save</strong></span>&nbsp;the&nbsp;<strong>deleted value</strong>&nbsp;in a&nbsp;<span style="color:#FF0000;"><strong><em>help</em>&nbsp;variable</strong></span>)</p> <p>&nbsp;</p> 
                    <hr><p>&nbsp;</p> </li> 
                   <li><span style="color:#0000FF;"><strong>Replace</strong></span>&nbsp;the&nbsp;<span style="color:#FF0000;"><strong><em>root</em>&nbsp;node</strong></span>&nbsp;with the&nbsp;<span style="color:#0000FF;"><strong><em>fartest</em>&nbsp;right node</strong></span>&nbsp;on the&nbsp;<strong>lowest levl</strong>: <p>&nbsp;</p> 
                    <table> 
                     <tbody> 
                      <tr> 
                       <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/HeapSort14b.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p>(We&nbsp;<span style="color:#0000FF;"><strong>save</strong></span>&nbsp;the&nbsp;<strong>deleted value</strong>&nbsp;in a&nbsp;<span style="color:#FF0000;"><strong><em>help</em>&nbsp;variable</strong></span>)</p> <p>&nbsp;</p> 
                    <hr><p>&nbsp;</p> </li> 
                   <li><span style="color:#0000FF;"><strong>Save</strong></span>&nbsp;the&nbsp;<span style="color:#FF0000;"><strong><em>deleted</em>&nbsp;value</strong></span>&nbsp;in the&nbsp;<span style="color:#0000FF;"><strong><em>empty</em>&nbsp;slot</strong></span>: (this slot is&nbsp;<span style="color:#0000FF;"><strong><em>not</em></strong></span>&nbsp;part of the&nbsp;<strong>Heap</strong>&nbsp;!!!) <p>&nbsp;</p> 
                    <table> 
                     <tbody> 
                      <tr> 
                       <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/HeapSort14c.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p>&nbsp;</p> 
                    <hr><p>&nbsp;</p> </li> 
                   <li><span style="color:#0000FF;"><strong>Fix</strong></span>&nbsp;the&nbsp;<span style="color:#FF0000;"><strong><em>Heap</em>&nbsp;</strong></span>using the&nbsp;<span style="color:#0000FF;"><strong>filter&nbsp;<em>down</em>&nbsp;algorithm</strong></span>: <p><span style="color:#0000FF;"><strong>Exchange</strong></span>&nbsp;the&nbsp;<strong>replacement node</strong>&nbsp;with its&nbsp;<span style="color:#FF0000;"><strong><em>smallest</em>&nbsp;child</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/HeapSort14d.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/HeapSort14e.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p>&nbsp;</p> <p><span style="color:#0000FF;"><strong>Exchange&nbsp;<em>again</em></strong></span>: (because one of its child node is&nbsp;<strong><em>smaller</em></strong>)</p> <p>&nbsp;</p> 
                    <table> 
                     <tbody> 
                      <tr> 
                       <td><img alt="" src="http://www.mathcs.emory.edu/~cheung/Courses/171/Syllabus/9-BinTree/FIGS/HeapSort14f.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/HeapSort14g.gif"></td> 
                      </tr> 
                     </tbody> 
                    </table><p>&nbsp;</p> </li> 
                  </ul></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> <p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
        --------------------
        
         
     *  **Notice that**:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> 
            <ul> 
             <li>The&nbsp;<span style="color:#0000FF;"><strong>value</strong></span>&nbsp;is&nbsp;<span style="color:#FF0000;"><strong>sorted&nbsp;<em>backwards</em></strong></span>&nbsp;in the&nbsp;<strong>back</strong>&nbsp;of the&nbsp;<span style="color:#0000FF;"><strong>array&nbsp;</strong></span>!!! <p><strong>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/HeapSort15.gif"></td> 
                </tr> 
               </tbody> 
              </table><p>&nbsp;</p> </li> 
            </ul></td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
        --------------------
        
         
     *  **Phase 2 algorithm** in **Pseudo code**:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><span style="color:#0000FF;"><strong> repeat these step N times (N = # nodes in the heap) { help = a[1]; // <span style="color:#FF0000;">Delete the root node</span> and save the value a[1] = a[last node in heap]; // <span style="color:#FF0000;">Replace root node</span> with // fartest right node on lowest level a[empty slot] = help; // <span style="color:#FF0000;">Save deleted value</span> in empty slot HeapFilterUp( 1 ); // <span style="color:#FF0000;">Fix the heap</span> start at root node } // Optionally, we can <span style="color:#FF0000;">reverse</span> the // array elements (because the values are sorted in reverse order) </strong></span></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
        --------------------
        
         
     *  **Phase 2 algorithm** in **Java**:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><span style="color:#0000FF;"><strong> for ( i = 1; i &lt; a.length; i++ ) { help = a[1]; // <span style="color:#FF0000;">Delete root node</span> a[1] = a[NNodes]; // <span style="color:#FF0000;">Replace root node with the last node</span> a[NNodes] = help; // <span style="color:#FF0000;">Put the deleted node in the empty slot<span style="color:#0000FF;"> NNodes--; // <span style="color:#FF0000;">One less node in Heap </span> HeapFilterDown(a, 1, NNodes); // <span style="color:#FF0000;">Fix the Heap</span> } /* ========================================================= This for-loop reverse the elements a[1] a[2] ... a[N] ========================================================= */ for ( i = 1, j = a.length-1; i &lt; j; i++, j-- ) { help = a[i]; a[i] = a[j]; a[j] = help; } </span></span></strong></span></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
         
    
     
    
    --------------------
    
    --------------------
    
    --------------------
    
    --------------------
    
     
 *  **The *complete* Heap Sort algorithm**
    
     
    
     *  Putting **phase 1** and **phase 2** into the **sort** method yields the following code:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><strong><span style="color:#0000FF;"> public static void <span style="color:#FF0000;">sort( double[] a )</span> { int i, j, NNodes; double help; <span style="color:#FF0000;"> /* ======================================= Phase 1 ======================================= */</span> <span style="color:#FF0000;">NNodes = 1;</span> for (i = 2; i &lt; a.length; i++) { <span style="color:#FF0000;">NNodes++;</span> // include next node HeapFilterUp(a, NNodes); printHeap(a, NNodes); } <span style="color:#FF0000;"> /* ======================================= Phase 2 ======================================= */</span> for ( i = 1; i &lt; a.length; i++ ) { help = a[1]; // Delete root node a[1] = a[NNodes]; // Replace root node with the last node a[NNodes] = help; // Put the deleted node in the empty slot <span style="color:#FF0000;">NNodes--;</span> // One less node in Heap HeapFilterDown(a, 1, NNodes); // Fix the Heap printHeap(a, NNodes); } </span>
              /* =======================================
                 Reverse the (sorted) array
        	 ======================================= */
              for ( i = 1, j = a.length-1; i &lt; j; i++, j-- )
              {
                 help = a[i];
                 a[i] = a[j];
                 a[j] = help;
              }
        
           }
        </strong></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
        --------------------
        
         
     *  The **Filter Up** method has been **changed** a **little** (because we must **pass** the **array** as a **parameter**)
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><span style="color:#0000FF;"><strong> The array <span style="color:#FF0000;">a</span> is passed as parameter The parameter <span style="color:#FF0000;">k</span> also to tell the method how many nodes there are in the Heap public static void HeapFilterUp( <span style="color:#FF0000;">double[] a</span>, int k ) { **** The BODY of the method is UNCHANGED !!!! **** } </strong></span></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
        (The ***algorithm*** did ***not*** change. --- that's why I **did *not*** include the ***body***)
        
        Only the ***way*** that the **array** is **given** to the **method** was **changed**
        
        This change does ***not*** (and **should** ***not***) affect you **understanding** of the **algorithm** !!!)
        
         
        
        --------------------
        
        --------------------
        
         
     *  The **Filter Down** method is ***also*** change a **little bit** due to the way the **parameters** are **passed**:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><span style="color:#0000FF;"><strong> The array <span style="color:#FF0000;">a</span> is passed as parameter The parameter <span style="color:#FF0000;">NNodes</span> is also needed to tell the method how many nodes there are in the Heap (k is the index of the delete location) public static void HeapFilterDown( <span style="color:#FF0000;">double[] a</span>, int k, <span style="color:#FF0000;">int NNodes</span> ) { **** The BODY of the method is UNCHANGED !!!! **** } </strong></span></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
        --------------------
        
         
     *  Here is a **test program** for the **Heap Sort** method:
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><span style="color:#0000FF;"><strong> public static void main( String[] args ) { double[] x = { <span style="color:#FF0000;">0,</span> 6.4, 2.5, 9.2, 3.5, 8.9, 1.1, 7.5, 4.2} ; System.out.println("Before sort: " + Arrays.toString(x) + "\n" ); HeapSort.sort( x ); // Heap sort System.out.println("\nAfter sort: " + Arrays.toString(x) ); } </strong></span></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
        **Output:**
        
         
        
        <table> 
         <tbody> 
          <tr> 
           <td> <pre><span style="color:#0000FF;"><strong>After sort: [<span style="color:#FF0000;">0.0,</span> 1.1, 2.5, 3.5, 4.2, 6.4, 7.5, 8.9, 9.2] </strong></span></pre> </td> 
          </tr> 
         </tbody> 
        </table>
        
         
        
        --------------------
        
         
     *  **Example Program: **(Demo above code)                                                 ![Example.jpg][]
        
         
        
         *  The **Heap Sort** Prog file: [click here][]
         *  The **test** Prog file: [click here][click here 1]
        
        **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>

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