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
AI-powered app for creating realistic nude photos

AI Clothes Remover
Online AI tool for removing clothes from photos.

Undress AI Tool
Undress images for free

Clothoff.io
AI clothes remover

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尊渡假赌尊渡假赌尊渡假赌
How Long Does It Take To Beat Split Fiction?
3 weeks agoByDDD
R.E.P.O. Save File Location: Where Is It & How to Protect It?
3 weeks agoByDDD

Hot Tools

Dreamweaver Mac version
Visual web development tools

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
Powerful PHP integrated development environment

SAP NetWeaver Server Adapter for Eclipse
Integrate Eclipse with SAP NetWeaver application server.

SublimeText3 English version
Recommended: Win version, supports code prompts!
