堆可以视为一棵完全的二叉树,完全二叉树的一个“优秀”的性质是,除了最底层之外,每一层都是满的,这使得堆可以利用数组来表示,每一个结点对应数组中的一个元素.大家知道PHP二叉堆是什么吗?下面就跟随小编一起来看看吧!
在以往工作或者面试的时候常会碰到一个问题，如何实现海量TopN，就是在一个非常大的结果集里面快速找到最大的前10或前100个数，同时要保证内存和速度的效率，我们可能第一个想法就是利用排序，然后截取前10或前100，而排序对于量不是特别大的时候没有任何问题，但只要量特别大是根本不可能完成这个任务的，比如在一个数组或者文本文件里有几亿个数，这样是根本无法全部读入内存的，所以利用排序解决这个问题并不是最好的，所以我们这里就用php去实现一个小顶堆来解决这个问题.
二叉堆
二叉堆是一种特殊的堆，二叉堆是完全二叉树或者是近似完全二叉树，二叉堆有两种，最大堆 和 最小堆，最大堆：父结点的键值总是大于或等于任何一个子节点的键值;最小堆：父结点的键值总是小于或等于任何一个子节点的键值
运行之后结果
可以看到最终的结果也是top10，只不过时间只用了1s左右，而且无论是内存还是时间效率都满足我们的要求，而且跟排序比最好的一点就是不用把所有的数据集都读如到内存里面来，因为我们不需要排序，而上面是为了演示，所以直接在内存构造了500w元素，然而我们可以把这个全部转移到文件里面去，然后一行一行读取进行比较，因为我们这个数据结构的核心点就是线性遍历跟内存里面很小的小顶堆结构进行比较，最终得到TopN.