search
Homephp教程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>);

 

Statement
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

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Repo: How To Revive Teammates
4 weeks agoBy尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Adventure: How To Get Giant Seeds
3 weeks agoBy尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Dreamweaver Mac version

Dreamweaver Mac version

Visual web development tools

Safe Exam Browser

Safe Exam Browser

Safe Exam Browser is a secure browser environment for taking online exams securely. This software turns any computer into a secure workstation. It controls access to any utility and prevents students from using unauthorized resources.

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

SAP NetWeaver Server Adapter for Eclipse

SAP NetWeaver Server Adapter for Eclipse

Integrate Eclipse with SAP NetWeaver application server.

SublimeText3 English version

SublimeText3 English version

Recommended: Win version, supports code prompts!