首页 / PHP / php实现堆排序

php实现堆排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了php实现堆排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1819字，纯文字阅读大概需要3分钟。

内容图文

             1
            abstract
            class
             Heap {

             2
            protected
            $elements = array();
 3protected$n = 0;
 4 5publicabstractfunction insert($element);
 6 7publicfunction isEmpty() {
 8return$this->n==0;
 9    }
1011publicfunction all(){
12return$this->elements;
13    }
1415/**
16     * Extract the top value of the heap
17     *
18*/19publicfunctionextract() {
20$element = $this->elements[1];
21$this->elements[1] = array_pop($this->elements);
22$this->n--;
23$this->siftDown();
24return$element;
25    }
2627/**
28     * Rearranges the heap after an extraction to keep the heap property
29*/30protectedabstractfunction siftDown();
3132/**
33     * Swap two elements on the elements array
34     *
35*/36protectedfunction swap($x,$y) {
37$tmp = $this->elements[$x];
38$this->elements[$x] = $this->elements[$y];
39$this->elements[$y] = $tmp;
40    }
41}
42class MinHeap extends Heap {
4344publicfunction insert($element) {
45$this->elements[++$this->n] = $element;
46for ($i = $this->n; $i > 1 && $this->elements[$i >> 1] > $this->elements[$i]; $i = $i >> 1)
47$this->swap($i >> 1,$i);
48    }
49protectedfunction siftDown() {
50for ($i = 1; ($c = $i * 2) <= $this->n; $i = $c) {
51//Checks which of the smaller child to compare with the parent52if ($c+1 <= $this->n && $this->elements[$c+1] < $this->elements[$c])
53$c++;
54if ($this->elements[$i] < $this->elements[$c])
55break;
56$this->swap($c, $i);
57        }
58    }
5960}
6162function heapSort($array){
63$heap=new MinHeap();
64foreach($arrayas$val){
65$heap->insert($val);
6667    }    
68$arr=array();
69while(!$heap->isEmpty()){
70$arr[]=$heap->extract();
71    }    
72return$arr;
73}
74$array=array(1,13,8,4,5);
75$arr=heapSort($array);
76print_r($arr);

 

原文：http://www.cnblogs.com/CHEUNGKAMING/p/4377449.html

内容总结

以上是互联网集市为您收集整理的php实现堆排序全部内容，希望文章能够帮你解决php实现堆排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/1215118.html

来源：【匿名】