Heim  >  Artikel  >  Backend-Entwicklung  >  PHP implementiert Heap-Sortierung

PHP implementiert Heap-Sortierung

WBOY
WBOYOriginal
2016-08-08 09:27:081073Durchsuche

Für das Konzept der Heap-Sortierung gehen Sie zu Baidu. Heute habe ich nichts zu tun und verwende PHP, um den Heap-Sortieralgorithmus zu implementieren

<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>);

Das Obige stellt die Implementierung der Heap-Sortierung in PHP vor, einschließlich ihrer Aspekte. Ich hoffe, dass es für Freunde hilfreich ist, die sich für PHP-Tutorials interessieren.

Stellungnahme:
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn