文档章节

php堆排序实现原理

baihan
 baihan
发布于 2013/10/14 02:20
字数 561
阅读 32
收藏 1
点赞 0
评论 0
<?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
博文 10
码字总数 2387
作品 0
深圳
高级程序员
常用8中排序算法Java实现与比较

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

NieJinliang ⋅ 2014/03/26 ⋅ 1

深入浅出 PHP SPL(PHP 标准库)

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

NateHuang ⋅ 06/08 ⋅ 0

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

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

biubiubiu! ⋅ 2016/10/09 ⋅ 0

PHP-利用二叉堆实现TopK-算法

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

简单方式 ⋅ 2017/04/23 ⋅ 0

笛卡尔积问题,求两数组有序对个数.

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

famince ⋅ 2014/08/22 ⋅ 3

深度剖析八大经典排序算法—C++实现(通俗易懂版)

内容会持续更新,有错误的地方欢迎指正,谢谢! 引言 该博客的示例代码均以递增排序为目的~ 学习建议:切忌看示例代码去理解算法,而是理解算法原理写出代码,否则会很快就会忘记。 算法分类 ...

billcyj ⋅ 2017/11/06 ⋅ 0

六大排序算法之 PHP和C++实现 - 算法思路解析

前言: 一直以来对于排序算法总有些熟悉又陌生的感觉,这几天看到一篇挺不错的博客讲排序的,http://blog.csdn.net/xiazdong/article/details/8462393 于是学习参考他的思路自己动手用php实现...

return_true_hang ⋅ 2017/03/08 ⋅ 0

常见排序算法及实现

一、冒泡排序 冒泡排序(Bubble Sort)是先从数组第一个元素开始,依次比较相邻两个数,若前者比后者 大,就将两者交换位置,然后处理下一对,依此类推,不断扫描数组,直到完成排序。 这个算...

thanatos_y ⋅ 2016/07/30 ⋅ 0

Java开发所需要知道的技术

1 Java基础 1.1 Collection和Map (1)掌握Collection和Map的继承体系。 (2)掌握ArrayList、LinkedList、Vector、Stack、PriorityQueue、HashSet、LinkedHashSet、TreeSet、HashMap、LinkedHas......

-wangming- ⋅ 2016/01/15 ⋅ 0

Java高级软件工程师面试考纲

1 Java基础 1.1 Collection和Map (1)掌握Collection和Map的继承体系。 (2)掌握ArrayList、LinkedList、Vector、Stack、PriorityQueue、HashSet、 LinkedHashSet、TreeSet、HashMap、LinkedH......

JackFace ⋅ 2016/08/08 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

从 Confluence 5.3 及其早期版本中恢复空间

如果你需要从 Confluence 5.3 及其早期版本中的导出文件恢复到晚于 Confluence 5.3 的 Confluence 中的话。你可以使用临时的 Confluence 空间安装,然后将这个 Confluence 安装实例升级到你现...

honeymose ⋅ 今天 ⋅ 0

用ZBLOG2.3博客写读书笔记网站能创造今日头条的辉煌吗?

最近两年,著名的自媒体网站今日头条可以说是火得一塌糊涂,虽然从目前来看也遇到了一点瓶颈,毕竟发展到了一定的规模,继续增长就更加难了,但如今的今日头条规模和流量已经非常大了。 我们...

原创小博客 ⋅ 今天 ⋅ 0

MyBatis四大核心概念

本文讲解 MyBatis 四大核心概念(SqlSessionFactoryBuilder、SqlSessionFactory、SqlSession、Mapper)。 MyBatis 作为互联网数据库映射工具界的“上古神器”,训有四大“神兽”,谓之:Sql...

waylau ⋅ 今天 ⋅ 0

以太坊java开发包web3j简介

web3j(org.web3j)是Java版本的以太坊JSON RPC接口协议封装实现,如果需要将你的Java应用或安卓应用接入以太坊,或者希望用java开发一个钱包应用,那么用web3j就对了。 web3j的功能相当完整...

汇智网教程 ⋅ 今天 ⋅ 0

2个线程交替打印100以内的数字

重点提示: 线程的本质上只是一个壳子,真正的逻辑其实在“竞态条件”中。 举个例子,比如本题中的打印,那么在竞态条件中,我只需要一个方法即可; 假如我的需求是2个线程,一个+1,一个-1,...

Germmy ⋅ 今天 ⋅ 0

Springboot2 之 Spring Data Redis 实现消息队列——发布/订阅模式

一般来说,消息队列有两种场景,一种是发布者订阅者模式,一种是生产者消费者模式,这里利用redis消息“发布/订阅”来简单实现订阅者模式。 实现之前先过过 redis 发布订阅的一些基础概念和操...

Simonton ⋅ 今天 ⋅ 0

error:Could not find gradle

一.更新Android Studio后打开Project,报如下错误: Error: Could not find com.android.tools.build:gradle:2.2.1. Searched in the following locations: file:/D:/software/android/andro......

Yao--靠自己 ⋅ 昨天 ⋅ 0

Spring boot 项目打包及引入本地jar包

Spring Boot 项目打包以及引入本地Jar包 [TOC] 上篇文章提到 Maven 项目添加本地jar包的三种方式 ,本篇文章记录下在实际项目中的应用。 spring boot 打包方式 我们知道,传统应用可以将程序...

Os_yxguang ⋅ 昨天 ⋅ 0

常见数据结构(二)-树(二叉树,红黑树,B树)

本文介绍数据结构中几种常见的树:二分查找树,2-3树,红黑树,B树 写在前面 本文所有图片均截图自coursera上普林斯顿的课程《Algorithms, Part I》中的Slides 相关命题的证明可参考《算法(第...

浮躁的码农 ⋅ 昨天 ⋅ 0

android -------- 混淆打包报错 (warning - InnerClass ...)

最近做Android混淆打包遇到一些问题,Android Sdutio 3.1 版本打包的 错误如下: Android studio warning - InnerClass annotations are missing corresponding EnclosingMember annotation......

切切歆语 ⋅ 昨天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部