php实现堆排序的原理如何理解？一文带你看明白
发布时间：2022-04-07 15:45:32 所属栏目：语言 来源：互联网
导读：很多新手在学习数据结构的时候，对于堆排序不是很理解，因此这篇文章就给大家介绍一下基于php实现堆排序的原理以及实例，有这方面学习需要的朋友可以参考学习。 堆(heap)是计算机科学中一类特殊的数据结构的统称，通常是一个可以被看做一棵树的数组对象。 堆
|
很多新手在学习数据结构的时候，对于堆排序不是很理解，因此这篇文章就给大家介绍一下基于php实现堆排序的原理以及实例，有这方面学习需要的朋友可以参考学习。 堆(heap)是计算机科学中一类特殊的数据结构的统称，通常是一个可以被看做一棵树的数组对象。 堆{k1,k2,ki,…,kn} (ki <= k2i,ki <= k2i+1)|(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2) 关于堆： 堆中某个节点的值总是不大于或不小于其父节点的值； 堆总是一棵完全二叉树（下面）。 将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。 完全二叉树 说到堆排序，就不能不提完全二叉树，这些基本概念在网上到处都是，我摘了个最简单的。 完全二叉树：除最后一层外，每一层上的节点数均达到最大值；在最后一层上只缺少右边的若干结点。 我自己总结认为，正是因为有下面两个特点， //此函数用来交换下数组$arr中下标为$one和$another的数据 function swap(&$arr,$one,$another){ $tmp=$arr[$one]; $arr[$one]=$arr[$another]; $arr[$another]=$tmp; } 下面是排序的最终结果： 堆用来进行全排序，时间复杂度是O(nlogn)，而快排用来全排序，平均时间复杂度也是O(nlogn)。但堆排序可以用来求 TopK 时，堆的时间复杂度为O(Klog2(n)，因为它只需要进行 K 轮排序即可。 （编辑：南通站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
