suchen
Heimphp教程php手册php实现堆排序,php堆排序

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

 

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

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

AI Hentai Generator

AI Hentai Generator

Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

R.E.P.O. Energiekristalle erklärten und was sie tun (gelber Kristall)
3 Wochen vorBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Beste grafische Einstellungen
3 Wochen vorBy尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. So reparieren Sie Audio, wenn Sie niemanden hören können
3 Wochen vorBy尊渡假赌尊渡假赌尊渡假赌
WWE 2K25: Wie man alles in Myrise freischaltet
4 Wochen vorBy尊渡假赌尊渡假赌尊渡假赌

Heiße Werkzeuge

VSCode Windows 64-Bit-Download

VSCode Windows 64-Bit-Download

Ein kostenloser und leistungsstarker IDE-Editor von Microsoft

Dreamweaver CS6

Dreamweaver CS6

Visuelle Webentwicklungstools

WebStorm-Mac-Version

WebStorm-Mac-Version

Nützliche JavaScript-Entwicklungstools

Sicherer Prüfungsbrowser

Sicherer Prüfungsbrowser

Safe Exam Browser ist eine sichere Browserumgebung für die sichere Teilnahme an Online-Prüfungen. Diese Software verwandelt jeden Computer in einen sicheren Arbeitsplatz. Es kontrolliert den Zugriff auf alle Dienstprogramme und verhindert, dass Schüler nicht autorisierte Ressourcen nutzen.

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung