图解-堆排序 in-place Heap Sort
转自：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 < 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 < 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 <strong>a[ ]</strong> to store the <strong>data</strong> that we want to <span style="color:#0000FF;"><strong>sort</strong></span> <p> </p><hr><p> </p> </li><li>The <span style="color:#FF0000;"><strong><em>Heap</em></strong></span> data structure (that we <span style="color:#0000FF;"><strong>create</strong></span> with the <span style="color:#FF0000;"><strong>new Heap(100)</strong></span>) <strong><em>also</em></strong> uses an <strong>array</strong> !!!</li></ul></td></tr></tbody></table>----------------------------------------* **Idea:**<table><tbody><tr><td><ul><li>Can we use the <strong><em>input</em> array</strong> <strong>a[ ]</strong> as a <span style="color:#FF0000;"><strong>Heap</strong></span> ??? <p>In other words:</p> <p> </p><table><tbody><tr><td><ul><li>Can we <span style="color:#0000FF;"><strong><em>apply</em></strong></span> the <span style="color:#FF0000;"><strong>heap <em>insert</em>/<em>delete</em> algorithm</strong></span> <strong><em>directly</em></strong> on the <strong>array</strong> <strong>a[ ]</strong> ???</li></ul></td></tr></tbody></table><p> </p> </li></ul></td></tr></tbody></table>--------------------------------------------------------------------------------
- Input data assumption
* **Facts:**<table><tbody><tr><td><ul><li>The <strong><em>input</em> data</strong> that will be <span style="color:#0000FF;"><strong><em>sorted</em></strong></span> are <strong><em>normally</em></strong> stored in an <strong>array</strong> that <span style="color:#FF0000;"><strong><em>starts</em></strong></span> with the <span style="color:#0000FF;"><strong>index 0</strong></span> in <strong>Java</strong> <p> </p><hr><p> </p> </li><li><span style="color:#FF0000;"><strong>However</strong></span>: <p> </p><table><tbody><tr><td><ul><li>When we <strong>use</strong> an <span style="color:#0000FF;"><strong><em>array</em></strong></span> to <span style="color:#FF0000;"><strong>represent</strong></span> a <strong>Heap</strong>, we <span style="color:#0000FF;"><strong>leave</strong></span> the array element <span style="color:#FF0000;"><strong>a[0]</strong></span> <strong><em>unused</em> (empty)</strong>...</li></ul></td></tr></tbody></table><p> </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 <strong><em>input</em> data</strong> that will be <span style="color:#0000FF;"><strong><em>sorted</em></strong></span> are stored in an <strong>array</strong> that <span style="color:#FF0000;"><strong><em>starts</em></strong></span> with the <span style="color:#0000FF;"><strong>index 1</strong></span> <p>(I.e., the array element <span style="color:#FF0000;"><strong>a[0]</strong></span> is <span style="color:#0000FF;"><strong><em>not</em> used</strong></span>)</p> </li></ul></td></tr></tbody></table>**Example:**<table><tbody><tr><td><ul><li>If we want to <span style="color:#0000FF;"><strong>sort</strong></span> the <strong>values</strong>: <p> </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 <strong>array</strong> with a <span style="color:#FF0000;"><strong><em>dummy</em> value</strong></span> in <span style="color:#0000FF;"><strong>a[0]</strong></span>:</p> <p> </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> </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> phase: <p> </p><table><tbody><tr><td><ul><li>In this phase, the <span style="color:#0000FF;"><strong><em>input</em> array</strong></span> is <strong>slowly</strong> transformed into a <span style="color:#FF0000;"><strong>Heap</strong></span> --- one <strong>array element</strong> at a time.</li></ul></td></tr></tbody></table><p> </p><hr><p> </p> </li><li><span style="color:#FF0000;"><strong>Heap teardown (<em>delete</em>)</strong></span> phase: <p> </p><table><tbody><tr><td><ul><li>In this phase, the <span style="color:#0000FF;"><strong><em>root</em> node</strong></span> of the <strong>Heap</strong> is <span style="color:#FF0000;"><strong><em>moved</em></strong></span> to the <span style="color:#0000FF;"><strong><em>back</em></strong></span> of the <strong>array</strong> and the <strong>heap</strong> is <span style="color:#0000FF;"><strong>torn down</strong></span>, one <strong>array element</strong> at a time.</li></ul></td></tr></tbody></table><p> </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 <span style="color:#0000FF;"><strong><em>heap</em> segment</strong></span> consisting of the <span style="color:#FF0000;"><strong>array elements</strong></span>: <p> </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 <strong>form</strong> a <span style="color:#FF0000;"><strong><em>Heap</em></strong></span></p> <p> </p><hr><p> </p> </li><li>A <span style="color:#FF0000;"><strong><em>unprocessed</em> segment</strong></span> of <span style="color:#0000FF;"><strong><em>unprocessed</em> array elements</strong></span>: <p> </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> </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> </p><table><tbody><tr><td><ul><li><strong>Step 1:</strong> <span style="color:#0000FF;"><strong>add</strong></span> the <span style="color:#FF0000;"><strong>next array element (a[2] = 4.2)</strong></span> to the <strong>Heap</strong> <p> </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> </p><hr><p> </p> </li><li><strong>Step 2:</strong> <span style="color:#0000FF;"><strong><em>Filter</em> </strong></span>the <span style="color:#FF0000;"><strong><em>newly added</em> next array element (a[2] = 4.2)</strong></span> <span style="color:#0000FF;"><strong>up</strong></span> into the <strong>Heap</strong> <p> </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> </p> </li></ul></td></tr></tbody></table><p> </p><hr><hr><p> </p> </li><li><strong>Iteration 2:</strong> <p> </p><table><tbody><tr><td><ul><li><strong>Step 1:</strong> <span style="color:#0000FF;"><strong>add</strong></span> the <span style="color:#FF0000;"><strong>next array element (a[3] = 1.1)</strong></span> to the <strong>Heap</strong> <p> </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> </p><hr><p> </p> </li><li><strong>Step 2:</strong> <span style="color:#0000FF;"><strong><em>Filter</em> </strong></span>the <span style="color:#FF0000;"><strong><em>newly added</em> next array element (a[3] = 1.1)</strong></span> <span style="color:#0000FF;"><strong>up</strong></span> into the <strong>Heap</strong> <p> </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> </p> </li></ul></td></tr></tbody></table><p> </p><hr><hr><p> </p> </li><li>One more and I will stop, <strong>Iteration 3:</strong> <p> </p><table><tbody><tr><td><ul><li><strong>Step 1:</strong> <span style="color:#0000FF;"><strong>add</strong></span> the <span style="color:#FF0000;"><strong>next array element (a[4] = 6.4)</strong></span> to the <strong>Heap</strong> <p> </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> </p><hr><p> </p> </li><li><strong>Step 2:</strong> <span style="color:#0000FF;"><strong><em>Filter</em> </strong></span>the <span style="color:#FF0000;"><strong><em>newly added</em> next array element (a[4] = 6.4)</strong></span> <span style="color:#0000FF;"><strong>up</strong></span> into the <strong>Heap</strong> <p> </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> </p> </li></ul></td></tr></tbody></table><p> </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 < 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 <span style="color:#0000FF;"><strong><em>Phase 1</em></strong></span> of the <strong>Heap Sort</strong> algorithm <span style="color:#FF0000;"><strong>completes</strong></span>, the <span style="color:#0000FF;"><strong><em>input</em> array (a[ ])</strong></span> will be <strong>transformed</strong> into a <span style="color:#FF0000;"><strong><em>Heap</em></strong></span></li></ul></td></tr></tbody></table>--------------------* **Example:**<table><tbody><tr><td><ul><li>Initial <span style="color:#0000FF;"><strong><em>input</em> array</strong></span>: <p> </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> </p><hr><p> </p> </li><li>When <span style="color:#0000FF;"><strong>phase 1</strong></span> completes, the <span style="color:#FF0000;"><strong>input array</strong></span> will be a <strong>Heap</strong>: <p> </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> </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 <span style="color:#0000FF;"><strong><em>root</em> node</strong></span> of the <strong>Heap</strong> is (always) stored in the <span style="color:#FF0000;"><strong>array element a[1]</strong></span> <p><strong>Example:</strong></p> <p> </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> </p> </li></ul></td></tr></tbody></table>--------------------* **Recall:**<table><tbody><tr><td><ul><li>When we <span style="color:#0000FF;"><strong>delete</strong></span> a <span style="color:#FF0000;"><strong>node</strong></span> from the <strong>Heap</strong>, we must <span style="color:#0000FF;"><strong>first</strong></span>: <p> </p><table><tbody><tr><td><ul><li><span style="color:#FF0000;"><strong><em>Replace</em></strong></span> the <strong>deleted node</strong> with the <span style="color:#0000FF;"><strong><em>right-most</em> leaf node</strong></span> in the <span style="color:#FF0000;"><strong><em>lowest</em> level</strong></span></li></ul></td></tr></tbody></table><p><strong>Example:</strong></p> <p> </p><table><tbody><tr><td><ul><li><strong><strong>When we <span style="color:#0000FF;"><strong>delete</strong></span> the <span style="color:#FF0000;"><strong>root node 1.1</strong></span>:</strong></strong> <p> </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> </p><hr><p> </p> </li><li><strong><strong>We <strong>first</strong> replace the <span style="color:#0000FF;"><strong>root node</strong></span> with the <span style="color:#FF0000;"><strong>node 6.4</strong></span>:</strong></strong> <p> </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> </p> </li></ul></td></tr></tbody></table><p> </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) <span style="color:#0000FF;"><strong>apply</strong></span> the <span style="color:#FF0000;"><strong>filter <em>down</em></strong></span> algorithm to <strong>fix</strong> the <span style="color:#0000FF;"><strong>tree</strong></span>... <p>(We will discuss that later...)</p> <p><span style="color:#FF0000;"><strong>But <em>more importantly</em></strong></span>, notice that:</p> <p> </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 <span style="color:#0000FF;"><strong>array</strong></span> has a <span style="color:#FF0000;"><strong><em>empty</em> slot</strong></span> at the <span style="color:#0000FF;"><strong>end</strong></span> !!!</p> <p> </p><table><tbody><tr><td><ul><li>We can <strong>use</strong> this <span style="color:#0000FF;"><strong><em>empty</em> slot</strong></span> to <strong>store</strong> the <span style="color:#FF0000;"><strong><em>deleted</em> value (1.1)</strong></span> !!! <p>(This <strong>trick</strong> makes the <strong>Heap Sort</strong> algorithm an <span style="color:#FF0000;"><strong><em>in-place</em> algorithm</strong></span> --- we don't need another array !!!)</p> </li></ul></td></tr></tbody></table><p> </p> </li></ul></td></tr></tbody></table>------------------------------------------------------------* This is what I mean:<table><tbody><tr><td><ul><li>We <strong>store</strong> the <span style="color:#FF0000;"><strong>deleted value</strong></span> into the <span style="color:#0000FF;"><strong><em>empty</em> slot</strong></span> created by the <span style="color:#FF0000;"><strong><em>replacement</em> step</strong></span> of the <span style="color:#0000FF;"><strong>Heap deletion algorithm</strong></span>: <p> </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> </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> </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> </p><hr><p> </p> </li><li><span style="color:#FF0000;"><strong>Filter down</strong></span>: <span style="color:#0000FF;"><strong>swap</strong></span> with the <span style="color:#FF0000;"><strong><em>smallest</em> child node</strong></span> <p> </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> </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> </p><hr><hr><p> </p> </li><li>Since <span style="color:#FF0000;"><strong>6.4</strong></span> is <span style="color:#0000FF;"><strong><em>smaller</em></strong></span> than its <span style="color:#FF0000;"><strong><em>children nodes</em> (9.2 and 7.5)</strong></span>, we have a <strong>Heap</strong> 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> (the previous iteration was the first iteration !) <p> </p><table><tbody><tr><td><ul><li><strong>Initially:</strong> <p> </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> </p><hr><p> </p> </li><li><span style="color:#0000FF;"><strong>Delete</strong></span> the <span style="color:#FF0000;"><strong><em>root</em> node (a[1])</strong></span>: <p> </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 <span style="color:#0000FF;"><strong>save</strong></span> the <strong>deleted value</strong> in a <span style="color:#FF0000;"><strong><em>help</em> variable</strong></span>)</p> <p> </p><hr><p> </p> </li><li><span style="color:#0000FF;"><strong>Replace</strong></span> the <span style="color:#FF0000;"><strong><em>root</em> node</strong></span> with the <span style="color:#0000FF;"><strong><em>fartest</em> right node</strong></span> on the <strong>lowest levl</strong>: <p> </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 <span style="color:#0000FF;"><strong>save</strong></span> the <strong>deleted value</strong> in a <span style="color:#FF0000;"><strong><em>help</em> variable</strong></span>)</p> <p> </p><hr><p> </p> </li><li><span style="color:#0000FF;"><strong>Save</strong></span> the <span style="color:#FF0000;"><strong><em>deleted</em> value</strong></span> in the <span style="color:#0000FF;"><strong><em>empty</em> slot</strong></span>: (this slot is <span style="color:#0000FF;"><strong><em>not</em></strong></span> part of the <strong>Heap</strong> !!!) <p> </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> </p><hr><p> </p> </li><li><span style="color:#0000FF;"><strong>Fix</strong></span> the <span style="color:#FF0000;"><strong><em>Heap</em> </strong></span>using the <span style="color:#0000FF;"><strong>filter <em>down</em> algorithm</strong></span>: <p><span style="color:#0000FF;"><strong>Exchange</strong></span> the <strong>replacement node</strong> with its <span style="color:#FF0000;"><strong><em>smallest</em> child</strong></span>:</p> <p> </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> </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> </p> <p><span style="color:#0000FF;"><strong>Exchange <em>again</em></strong></span>: (because one of its child node is <strong><em>smaller</em></strong>)</p> <p> </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> </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> </p> </li></ul></td></tr></tbody></table><p> </p> <p> </p> </li></ul></td></tr></tbody></table>----------------------------------------* **Notice that**:<table><tbody><tr><td><ul><li>The <span style="color:#0000FF;"><strong>value</strong></span> is <span style="color:#FF0000;"><strong>sorted <em>backwards</em></strong></span> in the <strong>back</strong> of the <span style="color:#0000FF;"><strong>array </strong></span>!!! <p><strong>Example:</strong></p> <p> </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> </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 < 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 < 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 < 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 < 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 < 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> on link and <span style="color:#FF0000;"><strong>save</strong></span> in a scratch directory <p> </p> </li><li>To compile: <span style="color:#FF0000;"><strong>javac testProg.java</strong></span></li><li>To run: <span style="color:#FF0000;"><strong>java testProg</strong></span></li></ul></td></tr></tbody></table>
偏执的太偏执、
今天药忘吃喽~
你的名字
还没有评论，来说两句吧...