php+堆排序算法,10大经典排序算法之堆排序（PHP版）

刺骨的言语ヽ痛彻心扉 2022-11-12 10:54 239阅读 0赞

堆排序，是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于(或者大于)它的父节点。大顶堆升序，小顶堆降序。

算法步骤

1、对原数组构建成大(小)顶堆，顶部就是最(小)值；

2、交换头尾值，最后一个值就是最大值，固定最(小)值；

3、然后索引减1，将最后一个值排除在外，用剩下的值继续构建大顶堆；

4、重复1-3步骤，直到堆中只剩一个，倒序的数组就出来了。

动图演示

![d68e685530b609bbaa24449765019f5b.gif][]

代码实现：public function heapSort($arr)

\{

$len = count($arr);

// 完全二叉树有一个性质：最后一个非叶结点是第n/2个结点。

for ($i = floor($len / 2); $i >= 0; $i --) \{

$this->heapify($arr, $i, $len);

\}

for ($i = count($arr) - 1; $i > 0; $i --) \{

$this->swap($arr, 0, $i);

$len --;

$this->heapify($arr, 0, $len); // 新的二叉树从上往下替换

\}

return $arr;

\}

/\*\*

\* 找出节点下的最大值

\*

\* @param array $arr   要排序的数组

\* @param int   $i     从什么位置开始找最大值

\* @param int   $len   堆的长度

\*/

private function heapify(&$arr, $i, $len)

\{

$left = 2 \* $i + 1;

$right = 2 \* $i + 2;

$largest = $i; // 默认节点就是最大值

if ($left  $arr\[$largest\]) \{ // 左叶子节点比最大值大，最大值就是左叶子节点

$largest = $left;

\}

if ($right  $arr\[$largest\]) \{ // 右叶子节点比最大值大，最大值就是右叶子节点

$largest = $right;

\}

if ($largest != $i) \{

$this->swap($arr, $i, $largest);

$this->heapify($arr, $largest, $len); // 从最大的节点位置往下继续替换，将小的值扔到子节点上去

\}

\}

//交换位置

private function swap(&$arr, $i, $j)

\{

$temp = $arr\[$i\];

$arr\[$i\] = $arr\[$j\];

$arr\[$j\] = $temp;

\}

[d68e685530b609bbaa24449765019f5b.gif]: /images/20221022/031f9d4336ea4c82b0e4684b6be3a057.png

发表评论取消回复

表情：

评论列表（有 0 条评论，239人围观）

还没有评论，来说两句吧...

相关阅读

相关 php实现数据排序算法,PHP实现排序堆排序算法

这篇文章主要为大家详细介绍了PHP实现排序堆排序(Heap Sort)算法，具有一定的参考价值，感兴趣的小伙伴们可以参考一下算法引进：在这里我直接引用《大话数据结构》里

素颜马尾好姑娘i/ 2023年01月15日 02:18/ 0 赞/ 115 阅读

相关 php+堆排序算法,10大经典排序算法之堆排序（PHP版）

堆排序，是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于(或者大于)它的父节点。大顶堆升序，小顶堆降

刺骨的言语ヽ痛彻心扉/ 2022年11月12日 10:54/ 0 赞/ 240 阅读

相关排序算法之堆排序

排序算法-----堆排序堆就是父节点值大于(大顶堆)子节点值或者父节点的值小于(小顶堆)子节点的值的完全二叉树，利用堆可以进行数组排序，如果要进行从小到大排序就

爱被打了一巴掌/ 2022年11月07日 04:13/ 0 赞/ 176 阅读

相关排序算法之堆排序

同样的先上这张图 ![Center][] 下面看一种较为复杂的选择排序 ——堆排序：首先来看一下什么是堆，堆用一个一维的数组模拟二叉树的结构，即堆数组的第一个元素

短命女/ 2022年09月25日 15:22/ 0 赞/ 193 阅读

相关排序算法之堆排序

堆排序> 在上一篇中提到了大小堆的问题，大小堆的一个应用就是堆排序，那仫什仫是堆排序呢？相对于我们经常使用的冒泡，选择以及直接插入排序，堆排序又存在什仫样不同的地方？我就

Love The Way You Lie/ 2022年07月16日 08:44/ 0 赞/ 201 阅读

相关排序算法之堆排序

问题描述：输入一个原始数列，把它进行升序排序，从小到大输出。例如：给定数列如下： 5 15 99 45 12 1 90 19 33 41 排序后的结果为： 1

雨点打透心脏的1/2处/ 2022年06月14日 02:39/ 0 赞/ 200 阅读

相关 php实现堆排序算法

最近在准备各种面试，复习了一波算法基础，关于什么是堆排序我就不多说了，这里说的很详细，不明白的可以参考一下： https://jingyan.baidu.com/articl

╰半夏微凉°/ 2022年06月04日 10:09/ 0 赞/ 180 阅读

相关八大排序算法之堆排序

例如数组 a=\{19,3,60,7,1,15,33,24,45,32,79,85\}; 排序思想： 1，堆排序也是选择排序的一种，根据堆得特性，每次把最大或最小值（本次以

待我称王封你为后i/ 2022年05月30日 02:38/ 0 赞/ 170 阅读

相关 JavaScript经典排序算法——堆排序

堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图： ![

╰+哭是因爲堅強的太久メ/ 2022年05月26日 07:10/ 0 赞/ 183 阅读

相关排序算法之堆排序

堆的定义：堆实际上是一棵完全二叉树。堆满足两个性质: 1. 堆的每一个父节点都大于（或小于）其子节点； 2. 堆的每个左子树和右子树也是一个堆。堆的每个左子树

柔情只为你懂/ 2022年04月16日 04:59/ 0 赞/ 250 阅读