堆、堆排序和TOPK

参考了该文章:https://www.jianshu.com/p/21bef3fc3030

什么是堆?

这是一种数据结构,完全二叉树(只有最下面一层的节点可以缺少右子节点,其余都是满节点)。
堆分为最大堆和最小堆:
最大堆:父节点的元素值总是大于等于子节点的元素值,所以堆顶元素是最大值
最小堆:父节点的元素值总是小于等于子节点的元素值,堆顶元素是最小值

最大堆和最小堆

节点位置和数组索引对应

数组索引从0开始,对于某个节点i,那么其父节点和子节点下标可以用公式表示:
父节点:floor(i/2)
左子节点:2xi + 1
右子节点:2xi + 2

如何将堆调整为最大/最小堆?

比如[4,1,3,2,16,9,10,14,8,7]

用层序遍历堆,将堆表现为数组形式
每个节点上方数字对应数组索引
假设节点个数为n=10
无论是最大堆或者最小堆,都从最后一个结点的父节点l开始往上调整。索引i=floor(n/2)-1=4

那么最大堆,就从这个i开始,和它的两个子节点中较大者比较,大则不变,小则互换,数组索引往前移;
如果最小堆,就从这个i开始,和它的两个子节点中较小者比较,小则不变,大则互换,数组索引往前移。

最小堆

  1. 从索引4开始,值为16,比子节点7大,则互换
  2. 此时节点16已经到底,索引4往前移,走到了3,i=3的节点和两个子节点中较小者比较,发现还是小,则不动;
  3. 此时索引移动到2,和步骤3一样,都比子节点小,不动;
  4. 索引移动到1,还是不动;
  5. 索引移动到0,根节点,和子节点最小者1互换;
  6. 互换后索引1节点再与子节点比较,与索引3互换 测试得到了最后结果:最小堆

php代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function minHeap(&$arrData, $intIdx)
{
$intLeftIdx = ($intIdx << 1) + 1;
$intRightIdx = ($intIdx << 1) +2;
if (!$arrData[$intLeftIdx]) {
return;
}
if ($arrData[$intRightIdx] && $arrData[$intRightIdx] < $arrData[$intLeftIdx]) {
$intMin = $intRightIdx;
} else {
$intMin = $intLeftIdx;
}
//节点和较小值节点互换
if ($arrData[$intIdx] > $arrData[$intMin]) {
$tmp = $arrData[$intIdx];
$arrData[$intIdx] = $arrData[$intMin];
$arrData[$intMin] = $tmp;
minHeap($arrData, $intMin);
}
}

最大堆

  1. 和最小堆类似,从索引4开始,比子节点较大者小,则互换,图中16比7大,则不动
  2. 此时索引往前到3,重复步骤1, 节点值2比14小,则互换
  3. 索引移到2,重复步骤1,节点值3和10互换
  4. 索引移到1,重复步骤1,节点值1和16互换
  5. 索引4不是叶子结点,和子节点对比,互换
  6. 此时索引移动到顶点0,重复步骤1,节点16和4互换
  7. 节点4和14互换
  8. 节点4和8互换 此时完成最大堆

php代码如下,和最小堆类似

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function maxHeap(&$arrData, $intIdx)
{
$intLeftIdx = ($intIdx << 1) + 1;
$intRightIdx = ($intIdx << 1) +2;
if (!$arrData[$intLeftIdx]) {
return;
}
if ($arrData[$intRightIdx] && $arrData[$intRightIdx] > $arrData[$intLeftIdx]) {
$intMax = $intRightIdx;
} else {
$intMax = $intLeftIdx;
}
//节点和较大值节点互换
if ($arrData[$intIdx] < $arrData[$intMax]) {
$tmp = $arrData[$intIdx];
$arrData[$intIdx] = $arrData[$intMax];
$arrData[$intMax] = $tmp;
maxHeap($arrData, $intMax);
}
}

TOPK

  • 用最小堆来实现topk算法
    比如求top5,先维护一个5个元素的数组,调整成最小堆,然后用剩余元素和最小堆的最小值比较,保持5元素的最小堆。在处理大量数据的时候,可以节省内存
    php实现如下:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    $numArr = array(4,1,3,2,16,9,10,14,8,7);
    $topArr = array_slice($numArr,0,5);
    //调整为最小堆
    $idx = floor(count($topArr) / 2) - 1;
    for($i=$idx;$i>=0;$i--){
    minHeap($topArr,$i);
    }
    //将剩余元素与之比较
    for ($i = count($topArr); $i < count($numArr); $i++) {
    if ($numArr[$i] > $topArr[0]) {
    $topArr[0] = $numArr[$i];
    }
    minHeap($topArr, 0);
    }
    var_dump($topArr);

堆排序

  1. 生成最小堆或者最大堆
  2. 将根节点与叶子结点可交换,堆长度减一
  3. 重复1、2步骤
    php实现:
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    $numArr = array(4,1,3,2,16,9,10,14,8,7);
    $len = count($numArr);
    $idx = floor($len/2) -1;
    for($i=$idx;$i>=0;$i--){
    minHeap($numArr,$i);
    }
    for ($i=$len-1; $i>0; $i--) {
    //最小值弹出
    $arrNew[] = array_shift($numArr);
    $len = count($numArr);
    if ($len == 1) {
    $arrNew[] = $numArr[0];
    continue;
    }
    //将最后一个节点移到根位置
    array_unshift($numArr, $numArr[$len-1]);
    array_pop($numArr);
    //重新调整成最小堆
    minHeap($numArr, 0);
    }
    var_dump($arrNew);

最大堆和最小堆类似

复杂度

堆用来进行全排序,时间复杂度是 O(nlogn)
快排用来全排序,平均时间复杂度也是 O(nlogn)
但堆排序可以用来求 TopK 时,堆的时间复杂度为 O(Klog2(n),因为它只需要进行 K 轮排序即可