«1. Обзор

В этом коротком руководстве мы увидим, как можно эффективно объединить отсортированные массивы с помощью кучи.

2. Алгоритм

Поскольку наша постановка задачи заключается в использовании кучи для слияния массивов, мы будем использовать мини-кучу для решения нашей задачи. Минимальная куча — это не что иное, как бинарное дерево, в котором значение каждого узла меньше значений его дочерних узлов.

Обычно min-heap реализуется с использованием массива, в котором массив удовлетворяет определенным правилам, когда речь идет о поиске родителя и потомка узла.

Для массива A[] и элемента с индексом i:

    A[(i-1)/2] вернет своего родителя A[(2*i)+1] вернет левого дочернего элемента A[ (2*i)+2] вернет правильный дочерний элемент

Вот изображение min-heap и его представление в виде массива:

Давайте теперь создадим наш алгоритм, который объединяет набор отсортированных массивов:

  1. Create an array to store the results, with the size determined by adding the length of all the input arrays.
  2. Create a second array of size equal to the number of input arrays, and populate it with the first elements of all the input arrays.
  3. Transform the previously created array into a min-heap by applying the min-heap rules on all nodes and their children.
  4. Repeat the next steps until the result array is fully populated.
  5. Get the root element from the min-heap and store it in the result array.
  6. Replace the root element with the next element from the array in which the current root is populated.
  7. Apply min-heap rule again on our min-heap array.

Наш алгоритм имеет рекурсивный поток для создания минимальной кучи, и мы должны посетить все элементы входных массивов.

Временная сложность этого алгоритма равна O(k log n), где k — общее количество элементов во всех входных массивах, а n — общее количество отсортированных массивов.

Давайте теперь посмотрим пример ввода и ожидаемый результат после запуска алгоритма, чтобы мы могли лучше понять проблему. Итак, для этих массивов: 

{ { 0, 6 }, { 1, 5, 10, 100 }, { 2, 4, 200, 650 } }

Алгоритм должен возвращать результирующий массив: 

{ 0, 1, 2, 4, 5, 6, 10, 100, 200, 650 }

3. Реализация Java

Теперь, когда у нас есть общее представление о том, что такое мини-куча и как происходит слияние Алгоритм работает, давайте посмотрим на реализацию Java. Мы будем использовать два класса — один для представления узлов кучи, а другой для реализации алгоритма слияния.

3.1. Представление узла кучи

Перед реализацией самого алгоритма давайте создадим класс, представляющий узел кучи. Здесь будет храниться значение узла и два вспомогательных поля: 

public class HeapNode {

    int element;
    int arrayIndex;
    int nextElementIndex = 1;

    public HeapNode(int element, int arrayIndex) {
        this.element = element;
        this.arrayIndex = arrayIndex;
    }
}

Обратите внимание, что мы намеренно опустили здесь геттеры и сеттеры, чтобы не усложнять задачу. Мы будем использовать свойство arrayIndex для хранения индекса массива, в котором берется текущий элемент узла кучи. И мы будем использовать свойство nextElementIndex для хранения индекса элемента, который мы возьмем после перемещения корневого узла в результирующий массив.

Изначально значение nextElementIndex будет равно 1. Мы будем увеличивать его значение после замены корневого узла min-heap.

3.2. Алгоритм слияния с минимальной кучей

Наш следующий класс должен представить саму мини-кучу и реализовать алгоритм слияния: 

public class MinHeap {

    HeapNode[] heapNodes;

    public MinHeap(HeapNode heapNodes[]) {
        this.heapNodes = heapNodes;
        heapifyFromLastLeafsParent();
    }

    int getParentNodeIndex(int index) {
        return (index - 1) / 2;
    }

    int getLeftNodeIndex(int index) {
        return (2 * index + 1);
    }

    int getRightNodeIndex(int index) {
        return (2 * index + 2);
    }

    HeapNode getRootNode() {
        return heapNodes[0];
    }

    // additional implementation methods
}

Теперь, когда мы создали наш класс с минимальной кучей, давайте добавим метод, который будет куча поддерева, где корневой узел поддерева находится в заданном индексе массива: 

void heapify(int index) {
    int leftNodeIndex = getLeftNodeIndex(index);
    int rightNodeIndex = getRightNodeIndex(index);
    int smallestElementIndex = index;
    if (leftNodeIndex < heapNodes.length 
      && heapNodes[leftNodeIndex].element < heapNodes[index].element) {
        smallestElementIndex = leftNodeIndex;
    }
    if (rightNodeIndex < heapNodes.length
      && heapNodes[rightNodeIndex].element < heapNodes[smallestElementIndex].element) {
        smallestElementIndex = rightNodeIndex;
    }
    if (smallestElementIndex != index) {
        swap(index, smallestElementIndex);
        heapify(smallestElementIndex);
    }
}

Когда мы используем массив для представления минимальной кучи, последний листовой узел всегда будет в конце массива . Таким образом, при преобразовании массива в мини-кучу путем итеративного вызова метода heapify() нам нужно только начать итерацию с родительского узла последнего листа: 

void heapifyFromLastLeafsParent() {
    int lastLeafsParentIndex = getParentNodeIndex(heapNodes.length);
    while (lastLeafsParentIndex >= 0) {
        heapify(lastLeafsParentIndex);
        lastLeafsParentIndex--;
    }
}

Наш следующий метод будет выполнять фактическую реализацию нашего алгоритма. . Для лучшего понимания давайте разделим метод на две части и посмотрим, как он работает: 

int[] merge(int[][] array) {
    // transform input arrays
    // run the minheap algorithm
    // return the resulting array
}

Первая часть преобразует входные массивы в массив узлов кучи, который содержит все элементы первого массива, и определяет размер результирующего массива: 

HeapNode[] heapNodes = new HeapNode[array.length];
int resultingArraySize = 0;

for (int i = 0; i < array.length; i++) {
    HeapNode node = new HeapNode(array[i][0], i);
    heapNodes[i] = node;
    resultingArraySize += array[i].length;
}

Следующая часть заполняет массив результатов, реализуя шаги 4, 5, 6 и 7 нашего алгоритма: 

MinHeap minHeap = new MinHeap(heapNodes);
int[] resultingArray = new int[resultingArraySize];

for (int i = 0; i < resultingArraySize; i++) {
    HeapNode root = minHeap.getRootNode();
    resultingArray[i] = root.element;

    if (root.nextElementIndex < array[root.arrayIndex].length) {
        root.element = array[root.arrayIndex][root.nextElementIndex++];
    } else {
        root.element = Integer.MAX_VALUE;
    }
    minHeap.heapify(0);
}

4. Тестирование алгоритма

Теперь давайте проверим наш алгоритм с тот же ввод, о котором мы упоминали ранее: 

int[][] inputArray = { { 0, 6 }, { 1, 5, 10, 100 }, { 2, 4, 200, 650 } };
int[] expectedArray = { 0, 1, 2, 4, 5, 6, 10, 100, 200, 650 };

int[] resultArray = MinHeap.merge(inputArray);

assertThat(resultArray.length, is(equalTo(10)));
assertThat(resultArray, is(equalTo(expectedArray)));

5. Заключение

В этом руководстве мы узнали, как эффективно объединять отсортированные массивы с помощью минимальной кучи.

Пример, который мы здесь продемонстрировали, можно найти на GitHub.