PHP利用二叉堆实现TopK-算法的方法详解

2024-05-04 22:48:00

字体：大中小

来源：转载

供稿：网友

前言

在以往工作或者面试的时候常会碰到一个问题，如何实现海量TopN，就是在一个非常大的结果集里面快速找到最大的前10或前100个数，同时要保证内存和速度的效率，我们可能第一个想法就是利用排序，然后截取前10或前100，而排序对于量不是特别大的时候没有任何问题，但只要量特别大是根本不可能完成这个任务的，比如在一个数组或者文本文件里有几亿个数，这样是根本无法全部读入内存的，所以利用排序解决这个问题并不是最好的，所以我们这里就用php去实现一个小顶堆来解决这个问题.

二叉堆

二叉堆是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树，二叉堆有两种，最大堆和最小堆，最大堆：父结点的键值总是大于或等于任何一个子节点的键值；最小堆：父结点的键值总是小于或等于任何一个子节点的键值

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

二叉堆一般用数组来表示（看上图），例如，根节点在数组中的位置是0，第n个位置的子节点分别在2n+1和 2n+2，因此，第0个位置的子节点在1和2，1的子节点在3和4，以此类推，这种存储方式便於寻找父节点和子节点。

具体概念问题这里就不在多说了，如果对二叉堆有疑问的可以在好好了解下这个数据结构，下面我们就针对上述topN问题来用php代码实现并解决，为了看出区别这里先用排序的方式去实现下看下效果如何。

利用快速排序算法来实现 TopN

//为了测试运行内存调大一点ini_set('memory_limit', '2024M');//实现一个快速排序函数function 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<$length;$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); }//构造500w不重复数for($i=0;$i<5000000;$i++){ $numArr[] = $i; }//打乱它们shuffle($numArr);//现在我们从里面找到top10最大的数var_dump(time());print_r(array_slice(quick_sort($all),0,10));var_dump(time());