Рубрики

Объединить k отсортированных массивов | Комплект 1

Учитывая k отсортированных массивов размером n каждый, объедините их и напечатайте отсортированный вывод.

Пример:

Input:
k = 3, n =  4
arr[][] = { {1, 3, 5, 7},
            {2, 4, 6, 8},
            {0, 9, 10, 11}} ;

Output: 0 1 2 3 4 5 6 7 8 9 10 11 

Простое решение — создать выходной массив размером n * k и скопировать по одному все массивы в него. Наконец, сортируйте выходной массив, используя любой алгоритм сортировки O (n Log n). Этот подход занимает O (nk Log nk) времени.

Одним из эффективных решений является первое слияние массивов в группы по 2. После первого слияния мы имеем k / 2 массивы. Мы снова объединяем массивы в группы, теперь у нас есть k / 4 массива. Мы продолжаем делать это, пока у нас остался один массив. Временная сложность этого решения будет O (nk Log k). Как? Каждое объединение в первой итерации будет занимать 2n времени (объединение двух массивов размера n). Поскольку существует общее слияние k / 2, общее время на первой итерации будет равно O (nk). Следующая итерация также займет O (nk). Всего будет O (Log k) итераций, следовательно, сложность по времени O (nk Log k)

Другим эффективным решением является использование Min Heap . Это решение на основе Min Heap имеет такую же временную сложность, как O (nk Log k). Но для массивов разных размеров это решение работает намного лучше.

Ниже приводится подробный алгоритм.
1. Создайте выходной массив размером n * k.
2. Создайте минимальную кучу размера k и вставьте 1-й элемент во все массивы в кучу.
3. Повторите следующие шаги n * k раз.
a) Получить минимальный элемент из кучи (минимум всегда в корне) и сохранить его в выходном массиве.
б) Замените корень кучи следующим элементом из массива, из которого этот элемент извлечен. Если в массиве больше нет элементов, замените корень на бесконечный. Заменив рут, поменяйте дерево.

Ниже приведена реализация вышеуказанного алгоритма.

C ++

// C ++ программа для объединения k отсортированных массивов размером n каждый.
#include<iostream>
#include<limits.h>

using namespace std;

  
#define n 4

  
// Узел минимальной кучи

struct MinHeapNode

{

    int element; // Элемент, который будет сохранен

    int i; // индекс массива, из которого взят элемент

    int j; // индекс следующего элемента, который будет выбран из массива

};

  
// Прототип служебной функции для замены двух минимальных узлов кучи

void swap(MinHeapNode *x, MinHeapNode *y);

  
// Класс для Min Heap

class MinHeap

{

    MinHeapNode *harr; // указатель на массив элементов в куче

    int heap_size; // размер кучи мин

public:

    // Конструктор: создает минимальную кучу заданного размера

    MinHeap(MinHeapNode a[], int size);

  

    // сложить поддерево с корнем по заданному индексу

    void MinHeapify(int );

  

    // получить индекс левого потомка узла по индексу i

    int left(int i) { return (2*i + 1); }

  

    // получить индекс правого потомка узла по индексу i

    int right(int i) { return (2*i + 2); }

  

    // чтобы получить рут

    MinHeapNode getMin() { return harr[0]; }

  

    // заменить корень новым узлом x и heapify () новым корнем

    void replaceMin(MinHeapNode x) { harr[0] = x;  MinHeapify(0); }

};

  
// Эта функция принимает массив массивов в качестве аргумента и
// Предполагается, что все массивы отсортированы. Это объединяет их
// и выводит окончательный отсортированный вывод.

int *mergeKArrays(int arr[][n], int k)

{

    int *output = new int[n*k];  // Для сохранения выходного массива

  

    // Создать минимальную кучу с k узлами кучи. Каждый узел кучи

    // имеет первый элемент массива

    MinHeapNode *harr = new MinHeapNode[k];

    for (int i = 0; i < k; i++)

    {

        harr[i].element = arr[i][0]; // Сохраняем первый элемент

        harr[i].i = i;  // индекс массива

        harr[i].j = 1;  // Индекс следующего элемента, который будет сохранен из массива

    }

    MinHeap hp(harr, k); // Создать кучу

  

    // Теперь один за другим получаем минимальный элемент из min

    // куча и заменить его следующим элементом массива

    for (int count = 0; count < n*k; count++)

    {

        // Получить минимальный элемент и сохранить его на выходе

        MinHeapNode root = hp.getMin();

        output[count] = root.element;

  

        // Найти следующий элемент, который заменит текущий

        // корень кучи. Следующий элемент принадлежит тому же

        // массив в качестве текущего корня.

        if (root.j < n)

        {

            root.element = arr[root.i][root.j];

            root.j += 1;

        }

        // Если корень был последним элементом своего массива

        else root.element =  INT_MAX; // INT_MAX для бесконечного

  

        // Заменить корень на следующий элемент массива

        hp.replaceMin(root);

    }

  

    return output;

}

  
// СЛЕДУЮЩИЕ РЕАЛИЗАЦИИ СТАНДАРТНЫХ МЕТОДОВ MIN MIN HEAP
// ИЗ КОРМЕНСКОЙ КНИГИ
// Конструктор: строит кучу из заданного массива a [] заданного размера

MinHeap::MinHeap(MinHeapNode a[], int size)

{

    heap_size = size;

    harr = a;  // сохранить адрес массива

    int i = (heap_size - 1)/2;

    while (i >= 0)

    {

        MinHeapify(i);

        i--;

    }

}

  
// Рекурсивный метод, чтобы накапливать поддерево с корнем по заданному индексу
// Этот метод предполагает, что поддеревья уже сложены

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);

    }

}

  
// Утилита для замены двух элементов

void swap(MinHeapNode *x, MinHeapNode *y)

{

    MinHeapNode temp = *x;  *x = *y;  *y = temp;

}

  
// Утилита для печати элементов массива

void printArray(int arr[], int size)

{

   for (int i=0; i < size; i++)

       cout << arr[i] << " ";

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    // Изменить n вверху, чтобы изменить количество элементов

    // в массиве

    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;

}

Джава

// Java программа для слияния и сортировки
// массивы размером n каждый.

  
// Узел минимальной кучи

class MinHeapNode

{

    int element; // Элемент, который будет сохранен

      

     // индекс массива из

     // какой элемент взят

    int i;

      

    // индекс следующего элемента

    // быть выбранным из массива

    int j; 

  

    public MinHeapNode(int element, int i, int j)

    {

        this.element = element;

        this.i = i;

        this.j = j;

    }

};

  
// Класс для Min Heap

class MinHeap

{

    MinHeapNode[] harr; // Массив элементов в куче

    int heap_size; // Текущее количество элементов в мин куче

  

    // Конструктор: строит кучу из

    // заданный массив a [] заданного размера

    public MinHeap(MinHeapNode a[], int size)

    {

        heap_size = size;

        harr = a;

        int i = (heap_size - 1)/2;

        while (i >= 0)

        {

            MinHeapify(i);

            i--;

        }

    }

  

    // Рекурсивный метод для подкачки поддерева

    // с корнем по заданному индексу

    // предполагает, что поддеревья уже накачаны

    void 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, smallest);

            MinHeapify(smallest);

        }

    }

  

    // получить индекс левого потомка узла по индексу i

    int left(int i) { return (2*i + 1); }

  

    // получить индекс правого потомка узла по индексу i

    int right(int i) { return (2*i + 2); }

  

    // чтобы получить рут

    MinHeapNode getMin() 

    {

        if(heap_size <= 0

        {

            System.out.println("Heap underflow");

            return null;

        }

        return harr[0];

    }

  

    // заменить корень новым узлом

    // "root" и heapify () новый корень

    void replaceMin(MinHeapNode root) {

        harr[0] = root;

        MinHeapify(0);

    }

  

    // Вспомогательная функция для замены двух минимальных узлов кучи

    void swap(MinHeapNode[] arr, int i, int j) {

        MinHeapNode temp = arr[i];

        arr[i] = arr[j];

        arr[j] = temp;

    }

  

    // Утилита для печати элементов массива

    static void printArray(int[] arr) {

        for(int i : arr)

            System.out.print(i + " ");

        System.out.println();

    }

  

    // Эта функция принимает массив

    // массивы в качестве аргумента и все

    // массивы предполагаются отсортированными.

    // объединяет их вместе и

    // выводит окончательный отсортированный вывод

    static void mergeKSortedArrays(int[][] arr, int k) 

    {

        MinHeapNode[] hArr = new MinHeapNode[k];

        int resultSize = 0;

        for(int i = 0; i < arr.length; i++) 

        {

            MinHeapNode node = new MinHeapNode(arr[i][0],i,1);

            hArr[i] = node;

            resultSize += arr[i].length;

        }

  

        // Создать минимальную кучу с k узлами кучи. Каждый узел кучи

        // имеет первый элемент массива

        MinHeap mh = new MinHeap(hArr, k);

  

        int[] result = new int[resultSize];     // Для сохранения выходного массива

  

        // Теперь один за другим получаем минимальный элемент из min

        // куча и заменить его следующим элементом массива

        for(int i = 0; i < resultSize; i++) 

        {

  

            // Получить минимальный элемент и сохранить его в результате

            MinHeapNode root = mh.getMin();

            result[i] = root.element;

  

            // Найти следующий элемент, который заменит текущий

            // корень кучи. Следующий элемент принадлежит тому же

            // массив в качестве текущего корня.

            if(root.j < arr[root.i].length)

                root.element = arr[root.i][root.j++];

            // Если корень был последним элементом своего массива

            else

                root.element = Integer.MAX_VALUE;

  

            // Заменить корень на следующий элемент массива

            mh.replaceMin(root);

        }

  

        printArray(result);

  

    }

  

    // Код драйвера

    public static void main(String args[]){

        int[][] arr= {{2, 6, 12, 34},

                {1, 9, 20, 1000},

                {23, 34, 90, 2000}};

  

        System.out.println("Merged array is :");

  

        mergeKSortedArrays(arr,arr.length);

    }

};

  
// Этот код предоставлен shubham96301

python3

«»»
Программа Python3 для объединения k отсортированных массивов размером n каждый
«»»

import sys

from typing import List, Optional

Matrix = List[List[int]]

  

  

class MinHeapNode:

    def __init__(self, el, i, j):

        self.element = el # элемент для сортировки

        self.i = i         # индекс массива, из которого взят элемент

        self.j = j         # индекс следующего элемента, который будет выбран из массива

  

  

class MinHeap:

    def __init__(self, ar: List[MinHeapNode], size: int):

        self.heap_size = size

        self.heap_arr = ar

        i = (self.heap_size - 1) // 2

        while i >= 0:

            self.min_heapify(i)

            i -= 1

  

    «»»

    Рекурсивный метод для подкачки поддерева

    с корнем по данному индексу. Этот метод

    предполагает, что поддерево уже навалено

    «»»

    def min_heapify(self, i):

        l = left(i)

        r = right(i)

        smallest = i

        if l < self.heap_size and self.heap_arr[l].element < self.heap_arr[i].element:

            smallest = l

        if r < self.heap_size and self.heap_arr[r].element < self.heap_arr[smallest].element:

            smallest = r

        if smallest != i:

            swap(self.heap_arr, i, smallest)

            self.min_heapify(smallest)

  

    def get_min(self) -> Optional:

        if self.heap_size <= 0:

            print('Heap underflow')

            return None

        return self.heap_arr[0]

  

    # Заменить root на новый root

    def replace_min(self, root):

        self.heap_arr[0] = root

        self.min_heapify(0)

  

  

def left(i):

    return 2 * i + 1

  

  

def right(i):

    return 2 * i + 2

  

  

def swap(arr: List[MinHeapNode], i, j):

    temp = arr[i]

    arr[i] = arr[j]

    arr[j] = temp

  

  

def merge_k_sorted_arrays(arr: Matrix, k: int):

    h_arr = []

    result_size = 0

    for i in range(len(arr)):

        node = MinHeapNode(arr[i][0], i, 1)

        h_arr.append(node)

        result_size += len(arr[i])

  

    min_heap = MinHeap(h_arr, k)

    result = [0]*result_size

    for i in range(result_size):

        root = min_heap.get_min()

        result[i] = root.element

        if root.j < len(arr[root.i]):

            root.element = arr[root.i][root.j]

            root.j += 1

        else:

            root.element = sys.maxsize

        min_heap.replace_min(root)

    for x in result:

        print(x, end=' ')

    print()

  

  

if __name__ == '__main__':

    arr = [

        [2, 6, 12, 34],

        [1, 9, 20, 1000],

        [23, 34, 90, 2000]

    ]

    print('Merged Array is:')

    merge_k_sorted_arrays(arr, len(arr))

  
# Код предоставлен Раджатом Шриваставой

C #

// C # программа для слияния и сортировки
// массивы размером n каждый.

using System;

  
// Узел минимальной кучи

public class MinHeapNode

{

    public int element; // Элемент, который будет сохранен

      

    // индекс массива из

    // какой элемент взят

    public int i;

      

    // индекс следующего элемента

    // быть выбранным из массива

    public int j; 

  

    public MinHeapNode(int element, int i, int j)

    {

        this.element = element;

        this.i = i;

        this.j = j;

    }

};

  
// Класс для Min Heap

public class MinHeap

{

    MinHeapNode[] harr; // Массив элементов в куче

    int heap_size; // Текущее количество элементов в мин куче

  

    // Конструктор: строит кучу из

    // заданный массив a [] заданного размера

    public MinHeap(MinHeapNode []a, int size)

    {

        heap_size = size;

        harr = a;

        int i = (heap_size - 1) / 2;

        while (i >= 0)

        {

            MinHeapify(i);

            i--;

        }

    }

  

    // Рекурсивный метод для подкачки поддерева

    // с корнем по заданному индексу

    // предполагает, что поддеревья уже накачаны

    void 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, smallest);

            MinHeapify(smallest);

        }

    }

  

    // получить индекс левого потомка узла по индексу i

    int left(int i) { return (2 * i + 1); }

  

    // получить индекс правого потомка узла по индексу i

    int right(int i) { return (2 * i + 2); }

  

    // чтобы получить рут

    MinHeapNode getMin() 

    {

        if(heap_size <= 0) 

        {

            Console.WriteLine("Heap underflow");

            return null;

        }

        return harr[0];

    }

  

    // заменить корень новым узлом

    // "root" и heapify () новый корень

    void replaceMin(MinHeapNode root)

    {

        harr[0] = root;

        MinHeapify(0);

    }

  

    // Вспомогательная функция для замены двух минимальных узлов кучи

    void swap(MinHeapNode[] arr, int i, int j) 

    {

        MinHeapNode temp = arr[i];

        arr[i] = arr[j];

        arr[j] = temp;

    }

  

    // Утилита для печати элементов массива

    static void printArray(int[] arr) 

    {

        foreach(int i in arr)

            Console.Write(i + " ");

        Console.WriteLine();

    }

  

    // Эта функция принимает массив

    // массивы в качестве аргумента и все

    // массивы предполагаются отсортированными.

    // объединяет их вместе и

    // выводит окончательный отсортированный вывод

    static void mergeKSortedArrays(int[,] arr, int k) 

    {

        MinHeapNode[] hArr = new MinHeapNode[k];

        int resultSize = 0;

        for(int i = 0; i < arr.GetLength(0); i++) 

        {

            MinHeapNode node = new MinHeapNode(arr[i, 0], i, 1);

            hArr[i] = node;

            resultSize += arr.GetLength(1);

        }

  

        // Создать минимальную кучу с k узлами кучи.

        // Каждый узел кучи имеет первый элемент массива

        MinHeap mh = new MinHeap(hArr, k);

  

        int[] result = new int[resultSize];     // Для сохранения выходного массива

  

        // Теперь один за другим получаем минимальный элемент

        // из минимальной кучи и заменить его на

        // следующий элемент его массива

        for(int i = 0; i < resultSize; i++) 

        {

  

            // Получить минимальный элемент и

            // сохранить в результате

            MinHeapNode root = mh.getMin();

            result[i] = root.element;

  

            // Найти следующий элемент, который будет

            // заменить текущий корень кучи.

            // Следующий элемент принадлежит тому же

            // массив в качестве текущего корня.

            if(root.j < arr.GetLength(1))

                root.element = arr[root.i,root.j++];

                  

            // Если корень был последним элементом своего массива

            else

                root.element = int.MaxValue;

  

            // Заменить корень на следующий элемент массива

            mh.replaceMin(root);

        }

        printArray(result);

    }

  

    // Код драйвера

    public static void Main(String []args)

    {

        int[,] arr = {{2, 6, 12, 34},

                      {1, 9, 20, 1000},

                      {23, 34, 90, 2000}};

  

        Console.WriteLine("Merged array is :");

  

        mergeKSortedArrays(arr, arr.GetLength(0));

    }

};

  
// Этот код предоставлен 29AjayKumar

Выход:

Merged array is
1 2 6 9 12 20 23 34 34 90 1000 2000

Сложность времени: основной шаг — 3-й шаг, цикл выполняется n * k раз. В каждой итерации цикла мы вызываем heapify, который занимает время O (Logk). Следовательно, временная сложность составляет O (nk Logk).

Объединить k отсортированных массивов | Набор 2 (разные размерные массивы)

Спасибо Vignesh за предложение этой проблемы и первоначальное решение. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Объединить k отсортированных массивов | Комплект 1

0.00 (0%) 0 votes