php實作堆排序

<span> 1</span> <span>abstract</span> <span>class</span><span> Heap {
</span><span> 2</span>     <span>protected</span> <span>$elements</span> = <span>array</span><span>();
</span><span> 3</span>     <span>protected</span> <span>$n</span> = 0<span>;
</span><span> 4</span>     
<span> 5</span>     <span>public</span> <span>abstract</span> <span>function</span> insert(<span>$element</span><span>);
</span><span> 6</span> 
<span> 7</span>     <span>public</span> <span>function</span><span> isEmpty() {
</span><span> 8</span>         <span>return</span> <span>$this</span>->n==0<span>;
</span><span> 9</span> <span>    }
</span><span>10</span>     
<span>11</span>     <span>public</span> <span>function</span><span> all(){
</span><span>12</span>         <span>return</span> <span>$this</span>-><span>elements;
</span><span>13</span> <span>    }
</span><span>14</span> 
<span>15</span>     <span>/*</span><span>*
</span><span>16</span> <span>     * Extract the top value of the heap
</span><span>17</span> <span>     *
</span><span>18</span>     <span>*/</span>
<span>19</span>     <span>public</span> <span>function</span> <span>extract</span><span>() {
</span><span>20</span>         <span>$element</span> = <span>$this</span>->elements[1<span>];
</span><span>21</span>         <span>$this</span>->elements[1] = <span>array_pop</span>(<span>$this</span>-><span>elements);
</span><span>22</span>         <span>$this</span>->n--<span>;
</span><span>23</span>         <span>$this</span>-><span>siftDown();
</span><span>24</span>         <span>return</span> <span>$element</span><span>;
</span><span>25</span> <span>    }
</span><span>26</span>     
<span>27</span>     <span>/*</span><span>*
</span><span>28</span> <span>     * Rearranges the heap after an extraction to keep the heap property
</span><span>29</span>      <span>*/</span>
<span>30</span>     <span>protected</span> <span>abstract</span> <span>function</span><span> siftDown();
</span><span>31</span> 
<span>32</span>     <span>/*</span><span>*
</span><span>33</span> <span>     * Swap two elements on the elements array
</span><span>34</span> <span>     *
</span><span>35</span>      <span>*/</span>
<span>36</span>     <span>protected</span> <span>function</span> swap(<span>$x</span>,<span>$y</span><span>) {
</span><span>37</span>         <span>$tmp</span> = <span>$this</span>->elements[<span>$x</span><span>];
</span><span>38</span>         <span>$this</span>->elements[<span>$x</span>] = <span>$this</span>->elements[<span>$y</span><span>];
</span><span>39</span>         <span>$this</span>->elements[<span>$y</span>] = <span>$tmp</span><span>;
</span><span>40</span> <span>    }
</span><span>41</span> <span>}
</span><span>42</span> <span>class</span> MinHeap <span>extends</span><span> Heap {
</span><span>43</span>     
<span>44</span>     <span>public</span> <span>function</span> insert(<span>$element</span><span>) {
</span><span>45</span>         <span>$this</span>->elements[++<span>$this</span>->n] = <span>$element</span><span>;
</span><span>46</span>         <span>for</span> (<span>$i</span> = <span>$this</span>->n; <span>$i</span> > 1 && <span>$this</span>->elements[<span>$i</span> >> 1] > <span>$this</span>->elements[<span>$i</span>]; <span>$i</span> = <span>$i</span> >> 1<span>)
</span><span>47</span>             <span>$this</span>->swap(<span>$i</span> >> 1,<span>$i</span><span>);
</span><span>48</span> <span>    }
</span><span>49</span>     <span>protected</span> <span>function</span><span> siftDown() {
</span><span>50</span>         <span>for</span> (<span>$i</span> = 1; (<span>$c</span> = <span>$i</span> * 2) <= <span>$this</span>->n; <span>$i</span> = <span>$c</span><span>) {
</span><span>51</span>             <span>//</span><span>Checks which of the smaller child to compare with the parent</span>
<span>52</span>             <span>if</span> (<span>$c</span>+1 <= <span>$this</span>->n && <span>$this</span>->elements[<span>$c</span>+1] < <span>$this</span>->elements[<span>$c</span><span>])
</span><span>53</span>                 <span>$c</span>++<span>;
</span><span>54</span>             <span>if</span> (<span>$this</span>->elements[<span>$i</span>] < <span>$this</span>->elements[<span>$c</span><span>])
</span><span>55</span>                 <span>break</span><span>;
</span><span>56</span>             <span>$this</span>->swap(<span>$c</span>, <span>$i</span><span>);
</span><span>57</span> <span>        }
</span><span>58</span> <span>    }
</span><span>59</span> 
<span>60</span> <span>}
</span><span>61</span> 
<span>62</span> <span>function</span> heapSort(<span>$array</span><span>){
</span><span>63</span>     <span>$heap</span>=<span>new</span><span> MinHeap();
</span><span>64</span>     <span>foreach</span>(<span>$array</span> <span>as</span> <span>$val</span><span>){
</span><span>65</span>         <span>$heap</span>->insert(<span>$val</span><span>);
</span><span>66</span>         
<span>67</span> <span>    }    
</span><span>68</span>     <span>$arr</span>=<span>array</span><span>();
</span><span>69</span>     <span>while</span>(!<span>$heap</span>-><span>isEmpty()){
</span><span>70</span>         <span>$arr</span>[]=<span>$heap</span>-><span>extract</span><span>();
</span><span>71</span> <span>    }    
</span><span>72</span>     <span>return</span> <span>$arr</span><span>;
</span><span>73</span> <span>}
</span><span>74</span> <span>$array</span>=<span>array</span>(1,13,8,4,5<span>);
</span><span>75</span> <span>$arr</span>=heapSort(<span>$array</span><span>);
</span><span>76</span> <span>print_r</span>(<span>$arr</span>);