php实现堆排序，php堆排序_PHP教程
- WBOY原創
- 2016-07-13 09:59:381216瀏覽
php实现堆排序，php堆排序
针对堆排序的概念自己百度去，今天没事了用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>);
陳述：
本文內容由網友自願投稿，版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容，請聯絡admin@php.cn