C++程序合并三个排序数组

在实际工作中，我们经常会面临将多个有序数组合并为一个有序数组的情况，这里我们来看一下如何在C++中实现合并三个有序数组。

思路分析

我们可以利用一个小根堆来进行合并，首先将三个数组的首个元素依次加入到小根堆中，然后每次从堆中选择最小的元素加入合并后的数组中，并将该元素在原数组中的下一个元素加入堆中，不断循环这个过程，直到堆为空。

代码实现

根据上述思路，我们先实现一个小根堆：

template <typename T>
class MinHeap {
public:
    MinHeap(const vector<T>& data) : heap(data) {
        for (int idx = heap.size() / 2 - 1; idx >= 0; --idx)
            sift_down(idx);
    }

    T pop() {
        T ans = heap[0];
        heap[0] = heap[heap.size() - 1];
        heap.pop_back();
        sift_down(0);
        return ans;
    }

    void push(const T& x) {
        heap.push_back(x);
        sift_up(heap.size() - 1);
    }

    inline bool empty() { return heap.empty(); }

private:
    vector<T> heap;

    inline int left(int idx) { return 2 * idx + 1; }
    inline int right(int idx) { return 2 * idx + 2; }
    inline int parent(int idx) { return (idx - 1) / 2; }

    void sift_down(int idx) {
        int i = idx, l = left(i), r = right(i), n = heap.size();
        if (l < n && heap[l] < heap[i]) i = l;
        if (r < n && heap[r] < heap[i]) i = r;
        if (i != idx) {
            swap(heap[idx], heap[i]);
            sift_down(i);
        }
    }

    void sift_up(int idx) {
        while (idx > 0 && heap[idx] < heap[parent(idx)]) {
            swap(heap[idx], heap[parent(idx)]);
            idx = parent(idx);
        }
    }
};

使用起来非常简单，只需要将要加入堆的元素一个一个push进去，然后每次用pop返回堆的最小元素即可。

接下来，我们就可以用这个堆来合并三个有序数组了：

vector<int> merge(const vector<int>& v1, const vector<int>& v2, const vector<int>& v3) {
    vector<int> ans;
    MinHeap<pair<int, int>> heap;
    int i = 0, j = 0, k = 0, n1 = v1.size(), n2 = v2.size(), n3 = v3.size();

    heap.push({v1[i], 0});
    heap.push({v2[j], 1});
    heap.push({v3[k], 2});

    while (!heap.empty()) {
        auto tmp = heap.pop();
        ans.push_back(tmp.first);
        if (tmp.second == 0 && i < n1) {
            heap.push({v1[++i], 0});
        } else if (tmp.second == 1 && j < n2) {
            heap.push({v2[++j], 1});
        } else if (tmp.second == 2 && k < n3) {
            heap.push({v3[++k], 2});
        }
    }

    return ans;
}

这里我们定义了一个pair类型的小根堆，pair的第一个元素为数组中的元素值，第二个元素则记录该元素是来自哪个数组，然后依次将三个数组的首个元素加入小根堆中，每次从堆中pop出最小的元素并加入合并后的数组中，然后将该元素在原数组中的下一个元素push进堆中，不断循环这个过程直到堆为空。