一、什么是堆 堆是一种非线性结构，可以把堆看作一棵二叉树，也可以看作一个数组，即：堆就是利用完全二叉树的结构来维护的一维数组。 堆可以分为大顶堆和小顶堆。 大顶堆：每个结点的值都大于或等于其左右孩子结点的值。 小顶堆：每个结点的值都小于或等于其左右孩子结点的值。 如果是排序，求升序用大顶堆，求降序用小顶堆。 一般我们说 topK 问题，就可以用大顶堆或小顶堆来实现， 最大的 K 个：小顶堆 最小的 K 个：大顶堆 二、大顶堆的构建过程 大顶堆的构建过程就是从最后一个非叶子结点开始从下往上调整。 最后一个非叶子节点怎么找？这里我们用数组表示待排序序列，则最后一个非叶子结点的位置是：数组长度/2-1。假如数组长度为9，则最后一个非叶子结点位置是 9/2-1=3。 比较当前结点的值和左子树的值，如果当前节点小于左子树的值，就交换当前节点和左子树； 交换完后要检查左子树是否满足大顶堆的性质，不满足则重新调整子树结构； 再比较当前结点的值和右子树的值，如果当前节点小于右子树的值，就交换当前节点和右子树； 交换完后要检查右子树是否满足大顶堆的性质，不满足则重新调整子树结构； 无需交换调整的时候，则大顶堆构建完成。 画个图理解下，以 [3, 7, 16, 10, 21, 23] 为例： 代码如下： <?php /** * 构建大顶堆 * 大顶堆的性质：每个结点的值都大于或等于其左右子结点的值。 */ function buildBigHeap(&$arr, $len) { for ($i = floor($len/2) – 1; $i >= 0; $i–) { //根节点小于左子树 if […]
时光荏苒，学无止境
