文档章节

php堆排序实现原理

baihan
 baihan
发布于 2013/10/14 02:20
字数 561
阅读 32
收藏 1
<?php
/**
php堆排序实现原理

php程序中关于堆的一些概念:
假设n为当前数组的key则
n的父节点为 n>>1 或者 n/2(整除);
n的左子节点l= n<<1 或 l=n*2,n的右子节点r=(n<<1)+1 或 r=l+1
*/
$arr=array(1,8,7,2,3,4,6,5,9);
/*
数组$arr的原形态结构如下:
             1
           /    \
         8      7
       /   \      / \
     2     3      4  6
    / \
   5  9
*/
heapSort($arr);
print_r($arr);
/*
排序后生成标准的小顶堆结构如下:
             1
           /   \
         2      3
       /   \    /  \
     4    5      6   7
    / \
   8  9
既数组:array(1,2,3,4,5,6,7,8,9)
*/
function heapSort(&$arr)
{
        //求最后一个元素位
        $last=count($arr);
        //堆排序中通常忽略$arr[0]
        array_unshift($arr,0);
        
        //最后一个非叶子节点
        $i=$last>>1;
        
        //整理成大顶堆,最大的数整到堆顶,并将最大数和堆尾交换,并在之后的计算中忽略数组后端的最大数(last),直到堆顶(last=堆顶)
        while(true)
        {
                adjustNode($i,$last,$arr);
                if($i>1)
                {
                        //移动节点指针,遍历所有非叶子节点
                        $i--;
                }
                else
                {
                        //临界点last=1,既所有排序完成
                        if($last==1)break;
                        //当i为1时表示每一次的堆整理都将得到最大数(堆顶,$arr[1]),重复在根节点调整堆
                        swap($arr[$last],$arr[1]);
                        //在数组尾部按大小顺序保留最大数,定义临界点last,以免整理堆时重新打乱数组后面已排序好的元素
                        $last--;
                }
        }
        //弹出第一个数组元素
        array_shift($arr);
}
//整理当前树节点($n),临界点$last之后为已排序好的元素
function adjustNode($n,$last,&$arr)
{
        $l=$n<<1;        //$n的左孩子位
        
        if(!isset($arr[$l])||$l>$last) return ;
        $r=$l+1;        //$n的右孩子位
        //如果右孩子比左孩子大,则让父节点的右孩子比
        if($r<=$last&&$arr[$r]>$arr[$l]) $l=$r;
        //如果其中子节点$l比父节点$n大,则与父节点$n交换
        if($arr[$l]>$arr[$n])                
        {
                //子节点($l)的值与父节点($n)的值交换
                swap($arr[$l],$arr[$n]);
                //交换后父节点($n)的值($arr[$n])可能还小于原子节点($l)的子节点的值,所以还需对原子节点($l)的子节点进行调整,用递归实现
                adjustNode($l,$last,$arr);
        }
}

//交换两个值
function swap(&$a,&$b)
{
        $a=$a ^ $b;        $b=$a ^ $b;        $a=$a ^ $b;
}

本文转载自:

共有 人打赏支持
下一篇: 常用排序方法
baihan
粉丝 1
博文 12
码字总数 2584
作品 0
深圳
高级程序员
私信 提问
常用8中排序算法Java实现与比较

一、常用的排序算法有如下几种: 1、冒泡排序 2、选择排序 3、插入排序 4、快速排序 5、堆排序 6、归并排序 7、计数排序 8、基数排序 接下来从原理、代码实现和测试三步对它们进行分析。 二、...

NieJinliang
2014/03/26
0
1
排序算法汇总——转载自http://blog.csdn.net/zhanglong_daniel/article/details/52513058

1. 冒泡排序 1.1 算法原理: S1:从待排序序列的起始位置开始,从前往后依次比较各个位置和其后一位置的大小并执行S2。 S2:如果当前位置的值大于其后一位置的值,就把他俩的值交换(完成一次...

biubiubiu!
2016/10/09
0
0
深入浅出 PHP SPL(PHP 标准库)

一、什么是spl库? SPL是用于解决典型问题(standard problems)的一组接口与类的集合。 此扩展只能在php 5.0以后使用,从PHP 5.3.0 不再被关闭,会一直有效.成为php内核组件一部份。 SPL提供了...

NateHuang
06/08
0
0
笛卡尔积问题,求两数组有序对个数.

某面试的算法题,笛卡尔积问题,求两个int数组组合成有序对(pair)个数有多少,如何最快时间计算出,手写实现CODE。 一开始还在回忆神马事笛卡尔积,不过面试官也稍微解释了下,奈何面试时有点...

famince
2014/08/22
275
3
PHP-利用二叉堆实现TopK-算法

介绍 在以往工作或者面试的时候常会碰到一个问题,如何实现海量TopN,就是在一个非常大的结果集里面快速找到最大的前10或前100个数,同时要保证内存和速度的效率,我们可能第一个想法就是利用...

简单方式
2017/04/23
0
0

没有更多内容

加载失败,请刷新页面

加载更多

Spring Cloud Stream消费失败后的处理策略(二):自定义错误处理逻辑

应用场景 上一篇《Spring Cloud Stream消费失败后的处理策略(一):自动重试》介绍了默认就会生效的消息重试功能。对于一些因环境原因、网络抖动等不稳定因素引发的问题可以起到比较好的作用...

程序猿DD
20分钟前
1
0
Java 使用 pinyin4j 生成汉字拼音

添加 pinyin4j jar包 <dependency> <groupId>com.belerweb</groupId> <artifactId>pinyin4j</artifactId> <version>2.5.0</version> ......

yh32
31分钟前
3
0
Deepin 安装wireshark抓包工具

一、关于deepin和wireshark deepin目前已经发展到15.8了,开发Android毫无压力,在四个月的使用时间里,已经非常习惯了。目前想处理一些网络问题,因此尝试在deepin上安装一个抓包工具。dee...

IamOkay
今天
6
0
Docker镜像仓库服务-Nexus

建立云原生集群系统,建立自己的私有Docker镜像仓库必不可少。一方面可以加快多节点部署容器镜像的下载速度,另一方面是为了安全(容器里存储有系统所有的信息、包括密码、数据库等等,切记不...

openthings
今天
6
0
127.0.0.1 和 0.0.0.0 地址的区别

1. IP地址分类 1.1 IP地址表示 IP地址由两个部分组成,net-id和host-id,即网络号和主机号。 net-id:表示ip地址所在的网络号。 host-id:表示ip地址所在网络中的某个主机号码。 即: IP-a...

华山猛男
今天
25
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部