Home > Backend Development > PHP Tutorial > PHP implements heap sorting, PHP heap sorting_PHP tutorial

PHP implements heap sorting, PHP heap sorting_PHP tutorial

WBOY
Release: 2016-07-13 09:59:38
Original
1225 people have browsed it

PHP implements heap sorting, php heap sorting

Go to Baidu for the concept of heap sorting. It’s okay today. Use PHP to implement heap sorting algorithm

<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>);
Copy after login

www.bkjia.comtruehttp: //www.bkjia.com/PHPjc/975481.htmlTechArticlePHP implements heap sorting. PHP heap sorting aims at the concept of heap sorting. Go to Baidu yourself. It’s okay today. Use PHP to implement heaping. Sorting algorithm 1 abstract class Heap { 2 protected $elements = array ();...
Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template