利用堆排序合并k个有序数组的PHP实现

Posted on | In | | Views:

网上有很多关于这个问题的讨论，最优的解法是利用堆排序进行合并，不过大多数是用C、Python等实现的，这里用PHP来实现。

代码

假设是从小到大排序，整体思路是构建一个大小为k(k为有序数组个数)的小根堆，堆里面存储的是每个数组当前的最小值，依次取出堆顶的元素存入结果集中，然后将该元素的下一个元素放到堆顶，重新进行堆排序，再取堆顶元素，不断循环，直到所有数组中的元素都存入结果集中。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
<?php

/**
 * @param array $arr 要合并的有序数组组成的二维数组
 * @return array
 */
function mergeKSortedArray($arr) {
    // 过滤掉空数组
    $arr = array_filter($arr, function ($v) {
        return empty($v) !== true;
    });
    if (empty($arr)) {
        return [];
    }
    // 如果有数组被过滤，原索引将不连续，所以要重建索引
    $arr = array_values($arr);
    // 让堆元素从下标1开始
    array_unshift($arr, []);
    // 构建初始堆
    $lastParentNode = floor((count($arr) - 1) / 2);   // 最后一个非叶子节点位置
    for ($i = $lastParentNode; $i > 0; $i--) {
        adjustHeap($arr, $i);
    }

    // 合并数组
    $mergedArr = [];
    while (!empty($arr[1])) {
        // 将第一个数组的当前元素(即堆顶)存入结果集中，
        $mergedArr[] = current($arr[1]);
        // 将第一个数组的内部指针移动到下一位，如果下一位没有元素，则删除该数组，后面的数组自动依次向前移动
        if (next($arr[1]) === false) {
            array_splice($arr, 1, 1);
        }
        if (empty($arr[1])) {
            break;
        }
        adjustHeap($arr, 1);
    }

    return $mergedArr;
}

/**
 * 构建小根堆
 */
function adjustHeap(&$arr, $i) {
    $len = count($arr);
    $arr[0] = $arr[$i];
    for ($k = $i * 2; $k <= $len - 1; $k *= 2) {
        if (($k + 1 <= $len - 1) && (current($arr[$k]) > current($arr[$k+1]))) {
            $k++;
        }
        if (current($arr[0]) < current($arr[$k])) {
            break;
        }
        $arr[$i] = $arr[$k];
        $i = $k;
    }
    $arr[$i] = $arr[0];
}

测试

用psysh引入上面的代码，测试如下：
测试结果