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>);
声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress
人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover
用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

Video Face Swap
使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热门文章
刺客信条阴影:贝壳谜语解决方案
1 个月前ByDDD
Windows 11 KB5054979中的新功能以及如何解决更新问题
3 周前ByDDD
在哪里可以找到原子中的起重机控制钥匙卡
1 个月前ByDDD
如何修复KB5055523无法在Windows 11中安装?
2 周前ByDDD
Inzoi:如何申请学校和大学
3 周前ByDDD

热工具

DVWA
Damn Vulnerable Web App (DVWA) 是一个PHP/MySQL的Web应用程序,非常容易受到攻击。它的主要目标是成为安全专业人员在合法环境中测试自己的技能和工具的辅助工具,帮助Web开发人员更好地理解保护Web应用程序的过程,并帮助教师/学生在课堂环境中教授/学习Web应用程序安全。DVWA的目标是通过简单直接的界面练习一些最常见的Web漏洞,难度各不相同。请注意,该软件中

EditPlus 中文破解版
体积小,语法高亮,不支持代码提示功能

MinGW - 适用于 Windows 的极简 GNU
这个项目正在迁移到osdn.net/projects/mingw的过程中,你可以继续在那里关注我们。MinGW:GNU编译器集合(GCC)的本地Windows移植版本,可自由分发的导入库和用于构建本地Windows应用程序的头文件;包括对MSVC运行时的扩展,以支持C99功能。MinGW的所有软件都可以在64位Windows平台上运行。

SecLists
SecLists是最终安全测试人员的伙伴。它是一个包含各种类型列表的集合,这些列表在安全评估过程中经常使用,都在一个地方。SecLists通过方便地提供安全测试人员可能需要的所有列表,帮助提高安全测试的效率和生产力。列表类型包括用户名、密码、URL、模糊测试有效载荷、敏感数据模式、Web shell等等。测试人员只需将此存储库拉到新的测试机上,他就可以访问到所需的每种类型的列表。

记事本++7.3.1
好用且免费的代码编辑器