PHP使用二进制堆实现TopK算法的详细说明

序

过去，在工作或面试时，我们经常会遇到一个问题。如何实现海量TopN，就是在非常大的结果集中快速找到最大的top 10或者top 100，同时保证内存的效率和速度。我们首先想到的可能是使用排序，然后截取前10名或者前100名。但是数量不是特别大的时候排序没有问题，但是只要数量特别大就不可能完成这个任务。比如一个数组或者文本文件中有上亿个数字，根本无法读入内存，所以排序不是解决这个问题的最好方法，所以我们用php实现了一个小的顶堆来解决这个问题。

两个交叉分支

二进制堆是一种特殊的堆，它是完全二叉树或近似完全二叉树。二进制堆有两种，最大堆和最小堆。最大堆：父节点的键值始终大于或等于任意子节点的键值；最小堆：父节点的键值总是小于或等于任何子节点的键值

小顶桩-(图片来自网络)

二进制堆通常由数组表示(见上文)。例如，数组中根节点为0，第n个位置的子节点分别为2n 1和2n 2。因此，第0个位置的子节点是1和2，1的子节点是3和4，以此类推。这种存储方式便于查找父节点和子节点。

这里具体的概念问题我就不多说了。如果您对二进制堆有任何问题，您可以很好地理解这个数据结构。现在我们将使用php代码来实现和解决上面的topN问题。为了看出区别，我们先用排序来实现。

利用快速排序实现TopN

//为了测试运行内存，放大ini_set('memory_limit '，' 2024m ')；//实现一个快速排序函数函数quick _ sort(array $ array){ $ length=count($ array)；$ left _ array=array()；$ right _ array=array()；if($ length=1){ return $ array；} $ key=$ array[0]；for($ I=1；$ i $长度；$ I){ if($ array[$ I]$ key){ $ right _ array[]=$ array[$ I]；} else { $ left _ array[]=$ array[$ I]；} } $ left _ array=quick _ sort($ left _ array)；$ right _ array=quick _ sort($ right _ array)；return array_merge($right_array，array($key)，$ left _ array)；}//构造$i=0的500w复数；$ i5000000$ I){ $ NuMarr[]=$ I；}//shuffle它们($ nu marr)；//现在我们找到top10最大数var _ dump(time())；print _ r(array _ slice(quick _ sort($ all)，0，10))；var _ dump(time())；

运行后的结果

可以看到上面打印了top10的结果，输出了下一个运行时间，大概是99s。但是，这只是文件数量为500w并且所有文件都可以加载到内存中的情况。如果我们有一个5kw或者5亿个文件的文件，肯定会有一些问题。

用二进制堆算法实现TopN

实现过程是：

1.首先将10或100个数字读入数组，这是我们的topN数。

2.调用生成小顶堆函数，从这个数组中生成一个小顶堆结构。此时，堆顶部必须是最小的。

3.依次遍历文件或数组中的所有剩余数字。

4.将每次遍历的大小与堆顶部的元素进行比较，如果小于堆顶部的元素，则将其丢弃，如果大于堆顶部的元素，则将其替换。

5.替换为堆的顶部元素后，通过调用生成小顶部堆函数继续生成小顶部堆，因为需要找到最小的一个。

6.重复以上4~5步，这样当所有遍历完成后，我们的小顶堆就是最大的topN，因为我们的小顶堆总是排除最小的，留下最大的，而且这个小顶堆的调整也很快，只是在相对调整下，只要根节点小于左右节点即可。

7.如果算法比较复杂，根据top10，最坏的情况是用堆顶替换需要调整10次，比排序速度快。而且不是所有的内容都读入内存，可以理解为线性遍历。

//生成小顶堆函数函数堆($ arr，$ idx){ $ left=($ idx 1)1；$ right=($ idx 1)2；if(！$ arr[$ left]){ return；} if($ arr[$ right]$ arr[$ right]$ arr[$ left]){ $ l=$ right；} else { $ l=$ left} if($ arr[$ idx]$ arr[$ l]){ $ tmp=$ arr[$ idx]；$ arr[$ idx]=$ arr[$ l]；$ arr[$ l]=$ tmp；Heap($arr，$ l)；} }//在这里，为了保证与上面的一致性，还构造了500w。/*当然，这个数据集不一定都在内存中，也可以在一个文件中，因为我们并不是都加载到内存中进行排序*/for($ I=0；$ i5000000$ I){ $ NuMarr[]=$ I；}//shuffle它们($ nu marr)；//首先取出10到数组$ topar=array _ slice($ numar，0，10)；//获取带有子节点的最后一个索引位置。//因为小的顶部堆是从最后一个位置用左或右节点构造的。//从下往上开始移动(详见上图)$ idx=floor(count($ topArr)/2)-1；//为($i=$idx)生成小的顶部堆；$ I=0；$i - ){ Heap($topArr，$ I)；} var _ dump(time())；//正如您在这里看到的，它是开始遍历所有剩余的元素为($ I=count($ topar)；$ I count($ NuMarr)；$i ){ //比较大小与顶部元素if ($numArr[$i] $topArr[0]){ //如果大于顶部元素，则替换$ Toparr[0]=$ Numarr[$ I]；/*再次调用生成小顶堆的函数进行维护，只是这一次，维护是从堆顶的索引位置从上到下进行的，因为我们只替换了堆顶的元素，其余的按照根节点小于左右节点的顺序放，这就是我们上面说的，但是只是在相对调整下，并不是所有的元素都被再次调整*/Heap($topArr，0)；} } var _ dump(time())；

运行后的结果

可以看到最终的结果也是top10，但是时间只需要1s左右，内存和时间效率都符合我们的要求。而且，和排序相比最好的一点是，我们不需要把所有的数据集都读入内存，因为我们不需要排序，但是上面是为了演示，所以我们直接在内存中构造500w的元素。但是，我们可以将所有这些元素转移到一个文件中，然后逐行读取它们进行比较，因为我们的数据结构的核心点是

摘要

最后我想说的是算法数据结构真的很重要，一个好的算法可以大大提高我们的效率。好了，这就是本文的全部内容。希望本文的内容能给你的学习或工作带来一些帮助。有问题可以留言交流。谢谢你的支持。