文档章节

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
深入浅出 PHP SPL(PHP 标准库)

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

NateHuang
06/08
0
0
排序算法汇总——转载自http://blog.csdn.net/zhanglong_daniel/article/details/52513058

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

biubiubiu!
2016/10/09
0
0
PHP-利用二叉堆实现TopK-算法

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

简单方式
2017/04/23
0
0
笛卡尔积问题,求两数组有序对个数.

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

famince
2014/08/22
263
3

没有更多内容

加载失败,请刷新页面

加载更多

下一页

angular 解决其他电脑不能访问的问题。

ng serve --host 0.0.0.0 --disable-host-check

miaojiangmin
今天
1
0
优酷视频文件怎么转换格式

  以前在优酷上下载视频都只是在手机上观看,但随着科技的发展,对于视频的要求也逐渐增多,不再只是观看视频那么简单,在精彩的部分还会将其单独分割出来,然后进行视频剪辑,可以做出我们...

萤火的萤火
今天
0
0
数据结构:散列

在一个数据结构中查找key元素,用顺序查找、二分查找都需要经过一系列关键之比较才能查找到结果,平均查找长度与数据量有关,元素越多比较次数就越多。 如果根据元素的关键字就能知道元素的存...

京一
今天
0
0
Apache RocketMQ 正式开源分布式事务消息

近日,Apache RocketMQ 社区正式发布4.3版本。此次发布不仅包括提升性能,减少内存使用等原有特性增强,还修复了部分社区提出的若干问题,更重要的是该版本开源了社区最为关心的分布式事务消...

阿里云云栖社区
今天
30
0
使用JavaScript和MQTT开发物联网应用

如果说Java和C#哪个是最好的开发语言,无疑会挑起程序员之间的相互怒怼,那如果说JavaScript是动态性最好的语言,相信大家都不会有太大的争议。随着越来越多的硬件平台和开发板开始支持JavaS...

少年不搬砖老大徒伤悲
今天
0
0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部