Skip to content

Merge k sorted arrays

geeksforgeeks Merge k sorted arrays | Set 1

NOTE:

1、其实和 leetcode 23. 合并K个升序链表 官方解题中给出的各种思路是一致的

Naive Approach: 暴力解法

// C++ program to merge k sorted arrays of size n each.
#include<bits/stdc++.h>
using namespace std;
#define n 4

// A utility function to print array elements
void printArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
}

// This function takes an array of arrays as an argument and
// All arrays are assumed to be sorted. It merges them together
// and prints the final sorted output.
void mergeKArrays(int arr[][n], int a, int output[])
{
    int c = 0;

    //traverse the matrix
    for (int i = 0; i < a; i++)
    {
        for (int j = 0; j < n; j++)
            output[c++] = arr[i][j];
    }

    //sort the array
    sort(output, output + n * a);

}

// Driver program to test above functions
int main()
{
    // Change n at the top to change number of elements
    // in an array
    int arr[][n] = { { 2, 6, 12, 34 }, { 1, 9, 20, 1000 }, { 23, 34, 90, 2000 } };
    int k = sizeof(arr) / sizeof(arr[0]);

    int output[n * k];

    mergeKArrays(arr, 3, output);

    cout << "Merged array is " << endl;
    printArray(output, n * k);

    return 0;
}
// g++ test.cpp -pedantic -Wall -Wextra --std=c++11

NOTE:

test.cpp:40:18: warning: ISO C++ forbids variable length array 'output' [-Wvla]

Efficient Approach 分治合并

// C++ program to merge k sorted arrays of size n each.
#include<bits/stdc++.h>
using namespace std;
#define n 4

// Merge arr1[0..n1-1] and arr2[0..n2-1] into
// arr3[0..n1+n2-1]
void mergeArrays(int arr1[], int arr2[], int n1, int n2, int arr3[])
{
    int i = 0, j = 0, k = 0;

    // Traverse both array
    while (i < n1 && j < n2)
    {
        // Check if current element of first
        // array is smaller than current element
        // of second array. If yes, store first
        // array element and increment first array
        // index. Otherwise do same with second array
        if (arr1[i] < arr2[j])
            arr3[k++] = arr1[i++];
        else
            arr3[k++] = arr2[j++];
    }

    // Store remaining elements of first array
    while (i < n1)
        arr3[k++] = arr1[i++];

    // Store remaining elements of second array
    while (j < n2)
        arr3[k++] = arr2[j++];
}

// A utility function to print array elements
void printArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
}

// This function takes an array of arrays as an argument and
// All arrays are assumed to be sorted. It merges them together
// and prints the final sorted output.
void mergeKArrays(int arr[][n], int i, int j, int output[])
{
    //if one array is in range
    if (i == j)
    {
        for (int p = 0; p < n; p++)
            output[p] = arr[i][p];
        return;
    }

    //if only two arrays are left them merge them
    if (j - i == 1)
    {
        mergeArrays(arr[i], arr[j], n, n, output);
        return;
    }

    //output arrays
    int out1[n * (((i + j) / 2) - i + 1)], out2[n * (j - ((i + j) / 2))];

    //divide the array into halves
    mergeKArrays(arr, i, (i + j) / 2, out1);
    mergeKArrays(arr, (i + j) / 2 + 1, j, out2);

    //merge the output array
    mergeArrays(out1, out2, n * (((i + j) / 2) - i + 1), n * (j - ((i + j) / 2)), output);

}

// Driver program to test above functions
int main()
{
    // Change n at the top to change number of elements
    // in an array
    int arr[][n] = { { 2, 6, 12, 34 }, { 1, 9, 20, 1000 }, { 23, 34, 90, 2000 } };
    int k = sizeof(arr) / sizeof(arr[0]);
    int output[n * k];
    mergeKArrays(arr, 0, 2, output);

    cout << "Merged array is " << endl;
    printArray(output, n * k);

    return 0;
}
// g++ test.cpp -pedantic -Wall -Wextra --std=c++11

Alternative Efficient Approach: The idea is to use Min Heap.

// C++ program to merge k sorted
// arrays of size n each.
#include<bits/stdc++.h>
using namespace std;

#define n 4

// A min-heap node
struct MinHeapNode
{
// The element to be stored
    int element;

// index of the array from which the element is taken
    int i;

// index of the next element to be picked from the array
    int j;
};

// Prototype of a utility function to swap two min-heap nodes
void swap(MinHeapNode *x, MinHeapNode *y);

// A class for Min Heap
class MinHeap
{

// pointer to array of elements in heap
    MinHeapNode *harr;

// size of min heap
    int heap_size;
public:
    // Constructor: creates a min heap of given size
    MinHeap(MinHeapNode a[], int size);

    // to heapify a subtree with root at given index
    void MinHeapify(int);

    // to get index of left child of node at index i
    int left(int i)
    {
        return (2 * i + 1);
    }

    // to get index of right child of node at index i
    int right(int i)
    {
        return (2 * i + 2);
    }

    // to get the root
    MinHeapNode getMin()
    {
        return harr[0];
    }

    // to replace root with new node x and heapify() new root
    void replaceMin(MinHeapNode x)
    {
        harr[0] = x;
        MinHeapify(0);
    }
};

// This function takes an array of arrays as an argument and
// All arrays are assumed to be sorted. It merges them together
// and prints the final sorted output.
int* mergeKArrays(int arr[][n], int k)
{

// To store output array
    int *output = new int[n * k];

    // Create a min heap with k heap nodes.
    // Every heap node has first element of an array
    MinHeapNode *harr = new MinHeapNode[k];
    for (int i = 0; i < k; i++)
    {

// Store the first element
        harr[i].element = arr[i][0];

// index of array
        harr[i].i = i;

// Index of next element to be stored from the array
        harr[i].j = 1;
    }

// Create the heap
    MinHeap hp(harr, k);

    // Now one by one get the minimum element from min
    // heap and replace it with next element of its array
    for (int count = 0; count < n * k; count++)
    {
        // Get the minimum element and store it in output
        MinHeapNode root = hp.getMin();
        output[count] = root.element;

        // Find the next elelement that will replace current
        // root of heap. The next element belongs to same
        // array as the current root.
        if (root.j < n)
        {
            root.element = arr[root.i][root.j];
            root.j += 1;
        }
        // If root was the last element of its array
// INT_MAX is for infinite
        else
            root.element = INT_MAX;

        // Replace root with next element of array
        hp.replaceMin(root);
    }

    return output;
}

// FOLLOWING ARE IMPLEMENTATIONS OF
// STANDARD MIN HEAP METHODS FROM CORMEN BOOK
// Constructor: Builds a heap from a given
// array a[] of given size
MinHeap::MinHeap(MinHeapNode a[], int size)
{
    heap_size = size;
    harr = a; // store address of array
    int i = (heap_size - 1) / 2;
    while (i >= 0)
    {
        MinHeapify(i);
        i--;
    }
}

// A recursive method to heapify a
// subtree with root at given index.
// This method assumes that the subtrees
// are already heapified
void MinHeap::MinHeapify(int i)
{
    int l = left(i);
    int r = right(i);
    int smallest = i;
    if (l < heap_size && harr[l].element < harr[i].element)
        smallest = l;
    if (r < heap_size && harr[r].element < harr[smallest].element)
        smallest = r;
    if (smallest != i)
    {
        swap(&harr[i], &harr[smallest]);
        MinHeapify(smallest);
    }
}

// A utility function to swap two elements
void swap(MinHeapNode *x, MinHeapNode *y)
{
    MinHeapNode temp = *x;
    *x = *y;
    *y = temp;
}

// A utility function to print array elements
void printArray(int arr[], int size)
{
    for (int i = 0; i < size; i++)
        cout << arr[i] << " ";
}

// Driver program to test above functions
int main()
{
    // Change n at the top to change number of elements
    // in an array
    int arr[][n] = { { 2, 6, 12, 34 }, { 1, 9, 20, 1000 }, { 23, 34, 90, 2000 } };
    int k = sizeof(arr) / sizeof(arr[0]);

    int *output = mergeKArrays(arr, k);

    cout << "Merged array is " << endl;
    printArray(output, n * k);

    return 0;
}

// g++ test.cpp -pedantic -Wall -Wextra --std=c++11

geeksforgeeks Merge K sorted arrays | Set 3 ( Using Divide and Conquer Approach )